力扣面试题 17.05. 字母与数字

这一道题和
力扣525.连续数组
思路一模一样。
都是把其中一种看作-1，另一种看作1，这样转化为找前缀和为0的子数组，比较简单，哈希表+前缀和解决

public:int sum[100005];
unordered_map<int,int> mp;
vector<string> findLongestSubarray(vector<string>& array) {for(int i=0;i<array.size();i++){if(array[i][0]>='0'&&array[i][0]<='9'){sum[i+1]=sum[i]-1;}else{sum[i+1]=sum[i]+1;}}mp[0]=0;int l=0;int r=0;int llmax=0;int rrmax=0;int maxx=0;for(int j=1;j<=array.size();j++){if(mp.count(sum[j])){r=j;l=mp[sum[j]];if(r-l>maxx){maxx=r-l;llmax=l;rrmax=r;}}else{mp[sum[j]]=j;}}return vector<string>(array.begin()+llmax,array.begin()+rrmax);}
};

但这一道题要注意的是返回值，如上代码写，比较方便，应该掌握
时间复杂度O(n)