LeetCode刷题实战525：连续数组-技术圈

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选！

今天和大家聊的问题叫做 连续数组，我们先来看题面：

https://leetcode-cn.com/problems/contiguous-array/

Given a binary array nums, return the maximum length of a contiguous subarray with an equal number of 0 and 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的最长连续子数组。

解题

https://www.cnblogs.com/geek1116/p/9389236.html

首先对原数组做处理，将所有的0都变为-1；这样一来 “含有相同数量的 0 和 1 的连续数组” 就等价为 “元素值总和为0的连续数组”。

其后，从头扫一遍数组，并记录当前的前缀和的值，将该值和对应的下标存入到一个标记数组或哈希表中。若该前缀和的值已出现过（即标记数组或哈希中已存在），则说明标记中的下标到当前扫描的下标的这段数组的总和值是为0的。

打个例子：[ -1，-1，-1，1，-1，1，-1，1，-1，-1，-1，-1 ] 在扫描完到第四个元素时，前缀和为-2 且未记录过，则将值-2和下标3记录起来。当扫描到 [ -1，-1，-1，1，-1，-1，1，1，-1，-1，-1，-1 ] ，此时得到的前缀和为-2，且知道标记中有记录过-2，则说明此刻下标到之前记录的下标的这段数组总和为0 [ -1，-1，-1，1，-1，-1，1，1，-1，-1，-1，-1 ] 。

class Solution {
    public int findMaxLength(int[] nums) {
        int ans = 0,sum = 0;
        for(int i=0;iif(nums[i]==0)nums[i]=-1;
        HashMap map = new HashMap();
        for(int i=0;i            sum+=nums[i];
            if(sum == 0) { if(i >= ans) ans = i+1; }
            if(map.get(sum) == null) { map.put(sum,i); continue; }
            int temp = i - map.get(sum);
            if(temp > ans) ans=temp;
        }
        return ans;
    }
}

好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力。

上期推文：

LeetCode1-520题汇总，希望对你有点帮助！

LeetCode刷题实战521：最长特殊序列 Ⅰ

LeetCode刷题实战522：最长特殊序列 II

LeetCode刷题实战523：连续的子数组和

LeetCode刷题实战524：通过删除字母匹配到字典里最长单词

​LeetCode刷题实战525：连续数组

示例

解题

LeetCode刷题实战525：连续数组