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

题目链接

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

题目描述

给定一个二进制数组 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<=10^5$
• nums[i]不是 0就是 1

分析

我们要找的子数组 1的个数 和 0的个数都相同。我们就可以把 0看成 -1从而将原问题转化为 求最长的一段区间和为 0的长度。

用 哈希表 记录某一个前缀和出现最早的下标因为我们求的是最长的区间长度遍历过程中不断更新答案。

时间复杂度$O(n)$

C++代码

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        unordered_map<int,int> umap;
        //添加 [0,-1] 是为了处理 出现从第一个元素开始就是合法子数组的情况
        //例如 [0,1,1,0,1,1,1] 此时前4个元素组成的区间和为0答案更新为 第四个元素的下标3 - umap[区间和(此时区间和为0)] = 3 - umap[0]
        // = 3 - (-1) = 4
         
        umap[0] = -1;
        int ans = 0;
        for(int i = 0,sum = 0;i < n;++i){
            sum += nums[i] == 1 ? 1 : -1;
            if(umap.count(sum)) ans = max(ans,i - umap[sum]);
            //只记录最早出现的下标
            else umap[sum] = i;
        }
        return ans;
    }
};

Java代码

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        Map<Integer,Integer> map = new HashMap<>();
        map.put(0,-1);
        int ans = 0;
        int sum = 0;
        for(int i = 0;i < n;++i){
            sum += nums[i] == 1 ? 1 : -1;
            
            if(map.containsKey(sum)) ans = Math.max(ans,i - map.get(sum));
            else map.put(sum,i);
        }
        return ans;
    }
}