类似题：Leetcode.560

题目描述

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

样例

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

(哈希表，前缀和) $O(n)$

1. 将数组中0视为-1，1视为1，求前缀和，问题转换为求最大长度的连续和为0的子数组；

2. 由于这里是求长度(不是方案数),哈希表里key存前缀和，value存下标，sum[i]==sum[j-1]+0,转化为hash.count(s),
   s为0-i的前缀和；

3.由于从0到n-1，所以只存s第一次在hash的出现的下标，其对应的下标最小，长度的计算公式为i-j,左闭右开

4.由于从0开始，sum[0]!=0,sum[-1]=0,因此将hash[0]初始化为-1（下标）

C++ 代码

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
    unordered_map<int,int> hash;
    int s=0,res=0;
    hash[0]=-1;
    for(int i=0;i<nums.size();i++)
    {
        s+=nums[i]?1:-1;
        if(hash.count(s)) res=max(res,i-hash[s]);
        else hash[s]=i;//
    }
    return res;
    }
};

c++代码(从1开始)

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