连续数组(哈希+前缀和)

这道题可以利用前缀和 + 哈希表来解决。

1.将 0 视为 -1

题目要求找“0 和 1 数目相等”的最长子数组。
如果把数组中的0当作-1，那就等价于：

找到一个子数组，使得这个子数组的元素和为 0。

2.使用哈希表记录前缀和第一次出现的位置

设prefixSum为从数组开始到当前的前缀和。

用unordered_map<int, int> index存储：

<前缀和，第一次出现的下标>

为什么存第一次出现的位置？
因为前缀和越早出现，后续遇到相同前缀和时形成的子数组就越长。

3.遍历数组时更新前缀和

扫描数组：

• 遇到1：prefixSum += 1

• 遇到0：prefixSum -= 1

每一步都检查：

如果当前前缀和 prefixSum 曾经出现过：

说明：

两次出现 prefixSum 之间的子数组和为 0
→ 0 和 1 的数量相等

于是可以计算当前长度并更新答案。

如果此前没有出现过 prefixSum：

记录当前下标（只记录第一次出现的位置）。

4.初始化 index[0] = -1

为了处理从下标0开始就满足条件的情况。

通过将 0 当作 -1，我们把问题转化为寻找“和为 0 的最长子数组”。
使用哈希表记录每个前缀和第一次出现的位置。当同一个前缀和再次出现时，说明中间的子数组和为 0，即 0 和 1 数量相等，从而可以更新最大长度。

class Solution { public: int findMaxLength(vector<int>& nums) { int cnt=0; unordered_map<int,int> index; index[cnt]=-1; int maxLen=0; for(int i=0;i<nums.size();i++){ if(nums[i]==1) cnt++; else cnt--; if(index.count(cnt)){ int curLen=i-index[cnt]; maxLen=maxLen>curLen?maxLen:curLen; } else index[cnt]=i; } return maxLen; } };