Description
给定二进制数组\(a\)，返回最长的0和1数目相同的子数组长度
Constraints
\(1 \le a.length \le 10^5\)
Solution
用表记录一下前缀和即可
前缀和指的是\(\{0 \to -1, 1 \to 1\}\)，这样和为\(0\)就代表0和1数目相同
每个相同的前缀和只取第一次，作差就能得到当前最长的情况
Code
class Solution {
public:
int findMaxLength(vector<int>& nums) {
// {presum, index}
std::unordered_map<int, int> rec;
int len = 0, sum = 0;
rec[0] = -1; // Note
for(int i = 0; i < nums.size(); ++i) {
int v = nums[i];
sum += (v ? 1 : -1);
if(rec.count(sum)) len = std::max(len, i - rec[sum]);
else rec[sum] = i;
}
return len;
}
};