给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

示例 1:

输入: [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。

示例 2:

输入: [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

注意: 给定的二进制数组的长度不会超过50000。

Solution

参考：@ffreturn

问题转换

• 为了让0和1相等，把0变为-1，那么就是对应数组求和为0即可，于是可以转换为前缀和

思路

• 计算前缀和
• 遍历i每次去找前面和自己一样的前缀和对应的编号j，那么差值必然为0，这个数组大小就是 i-j

由于求的是最长区间，因此就需要记录前缀和的数值第 1 次出现的下标，相同的前缀再次出现，就说明这一段区间的和为 0（把 0 看成 -1 以后），在遍历的过程中，记录最长的区间的长度；

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        if (n < 2) return 0;

        vector<int> preSum(n+1, 0); // 注意前缀和的计算形式
        for (int i = 1; i <= n; ++i) {
            preSum[i] = preSum[i-1] + (nums[i-1] == 0 ? -1 : 1);
        }

        // 记录每个preSum对应的最小的编号
        unordered_map<int, int> sum2index;
        int res = 0;
        for (int i = 0; i <= n; ++i) {
            if (sum2index.find(preSum[i]) != sum2index.end()) {
                res = max(res, i - sum2index[preSum[i]]);
            } else {
                sum2index[preSum[i]] = i;
            }
        }
        return res;
    }
};