一.剑指 Offer II 011. 0 和 1 个数相同的子数组

1.题干及思路

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1:

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

示例 2:

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

提示：

• 1 <= nums.length <= 105
• nums[i] 不是 0 就是 1

注意：本题与主站 525 题相同： https://leetcode-cn.com/problems/contiguous-array/

要点：前缀和

思路：用哈希表加前缀和来做，哈希表的key为前缀和，value为该前缀和第一次出现的下标，遍历数组对于每个nums[i]如果是0就减1，是1就加1，如果哈希表找到该key那么 ans = max(ans,i-m[cur])

2.C++实现

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