---

题目链接：

525. 连续数组

---

题目描述：

---

解法

前缀和思想：

如果把0变成-1，那么就是在区间内找一个最长的子数组，使得子数组中所有元素的和为0

前面做过一个前缀和为k的子数组，这里就是转化为和为0。

前缀和+哈希表

1. 哈希表里面存什么？

前面那题哈希表里面两个元素是前缀和+个数，但这里不要个数，要最长的。

所以哈希表里面存放：前缀和+下标

2. 什么时候存入哈希表？

使用完之后，丢进哈希表

3. 如果有重复的<sum,i>如何存储？

遇到长的，就把短的替换掉。

4. 默认的前缀和为0的情况怎么存？

hash[0] = -1;

5. 长度怎么算?

i-j+1-1=i-j

---

C++ 算法代码：

class Solution 
{
    public:
    int findMaxLength(vector<int>& nums) 
    {
        unordered_map<int, int> hash;
        hash[0] = -1; // 默认有一个前缀和为 0 的情况
        int sum = 0, ret = 0;
        for(int i = 0; i < nums.size(); i++)
        {
            sum += nums[i] == 0 ? -1 : 1; // 计算当前位置的前缀和
            if(hash.count(sum)) ret = max(ret, i - hash[sum]);
            else hash[sum] = i;
        }
        return ret;
    }
};

---

图解

例如：nums = [0,1,0]

1. hash[0] = -1，sum = 0, ret = 0

   进入for循环，

   i = 0 (nums[0] = 0):

   • sum += -1 → sum = -1
   • 检查 hash 中是否存在 sum = -1（不存在）
   • 将 sum = -1 和 i = 0 存入 hash → hash = {0: -1, -1: 0}
   • ret 保持为 0

   i = 1 (nums[1] = 1):

   • sum += 1 → sum = 0
   • 检查 hash 中是否存在 sum = 0（存在，值为 -1）
   • 更新 ret 为 max(0, 1 - (-1)) → ret = 2
   • hash 中 sum = 0 的值保持不变（因为已经存在）
   • ret = 2

   i = 2 (nums[2] = 0):

   • sum += -1 → sum = -1
   • 检查 hash 中是否存在 sum = -1（存在，值为 0）
   • 更新 ret 为 max(2, 2 - 0) → ret = 2
   • hash 中 sum = -1 的值保持不变（因为已经存在）
   • ret = 2

2. 返回 ret = 2，即最长包含相同数量 0 和 1 的子数组长度是 2，对应的子数组是 [0, 1] 或 [1, 0]