字母与数字
- 难度：Medium
- 题目链接：https://leetcode-cn.com/problems/find-longest-subarray-lcci/
题目描述
给定一个放有字符和数字的数组，找到最长的子数组，且包含的字符和数字的个数相同。
返回该子数组，若存在多个最长子数组，返回左端点最小的。若不存在这样的数组，返回一个空数组。
示例 1:
输入: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7","H","I","J","K","L","M"] 输出: ["A","1","B","C","D","2","3","4","E","5","F","G","6","7"]
示例 2:
输入: ["A","A"] 输出: []
提示：
array.length <= 100000
解法：
从左至右计算前缀和，数字视为 1 字母视为 -1，保存前缀和与下标的映射关系。如果下标 i 处前缀和为 +3，找到之前出现前缀和为 +3 的下标 j，那么 j ~ i 之间的和为 0。这个区间内字母的数量和数字的数量相同。
class Solution {
public:
vector<string> findLongestSubarray(vector<string>& array) {
unordered_map<int, int> mp;
int n = 0;
int start = 0, max_len = 0;
mp[0] = 0;
for(int i=0;i<array.size();i++){
if(isdigit(array[i][0])){
n++;
}else{
n--;
}
if(mp.find(n) == mp.end()){
mp[n] = i+1;
}else{
if(i - mp[n] + 1 > max_len){
start = mp[n];
max_len = i - mp[n] + 1;
}
}
}
return vector<string>(array.begin() + start, array.begin() + start + max_len);
}
};