11

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

1 题目描述

• 题目链接：剑指 Offer II 011. 0 和 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 的最长连续子数组。

2 思路

  将0看作-1，然后转换为求前缀和的问题。用一个哈希表存储前缀和数组。

• 当前缀和为0时，说明从起点到当前位置的连续序列中0和1的数量相等，因而更新答案为原答案和当前已经遍历的数字位数间的大者, 即ans = max(ans, i + 1)，i为当前遍历到的数字索引。
• 当前缀和不为0时，为找到连续序列中0和1的数量相等，那么在哈希表中查找这个前缀和，如果找到了，则将答案更新为原答案和该序列的长度中的大者，即ans = max(ans, i - it->second)，这里的it实际上就是指向哈希表中该前缀和出现的位置的指针，而it->second即为其下标。

class Solution {
    unordered_map<int, int> m;
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        int sum = 0, ans = 0;
        for(int i = 0; i < n; ++i){
            if(nums[i] == 0){
                sum -= 1;
            }else{
                sum += 1;
            }
            if(sum == 0){
                ans = max(ans, i+1);
            }else{
                auto it = m.find(sum);
                if(it == m.end()){
                    m.insert({sum, i});
                }else{
                    ans = max(ans, i - it->second);
                }
            }
        }
        return ans;
    }
};