525 连续数组（前缀和、哈希表）

向右看齐 2022-08-30 06:21 170阅读 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的最长连续子数组。

**提示：**

1 <= nums.length <= 10 ^ 5  
nums\[i\]不是0就是 1  
来源：力扣（LeetCode）  
链接：https://leetcode-cn.com/problems/contiguous-array

**2. 思路分析：**

对于这种题目我们首先需要考虑怎么样才可以枚举出所有的答案， 一般是枚举以当前的i为终点的...对于这道题目来说也是类似的我们可以枚举以当前位置为i结尾的所有0和1的数目相等的区间，其实我们并不关心0和1具体的数目我们关心的是0和1数目的差值，如果差值为0那么当前区间0和1的数目相等，如果差值不为0说明0和1的数目是不相等的，如何快速判断某个区间0和1的数目的差值是否相等呢？类似于力扣的523题我们也可以使用**前缀和**解决，只是这里的前缀和的含义为当前1的数目减去0的数目的差值，我们可以在遍历的时候来维护这个前缀和，也即使用两个变量zero，one表示当前0和1的数目，one - zero就是当前\[1, i\]0和1数目的差值，如何找到以当前位置i结尾的1的数目减去0的数目差值为0的区间呢？可以发现如果之前\[1, j\]中1的数目减去0的数目的差值等于当前\[1, i\]中1的数目减去0的数目的差值，说明当前区间\[j + 1, i\]中1的数目减去0的数目的差值是为0的。这样问题就转化为了如何快速判断之前是否存在某一个值？这里可以使用哈希表来存储遍历的时候1的数目减去0的数目的差值对应的位置，由于求解的是最长的连续子数组所以我们在哈希表中存储的是两者差值最开始的那个位置，这样当求解的出的肯定是最长的满足要求的连续子数组。

**3. 代码如下：**

from typing import List
    
    
    class Solution:
        def findMaxLength(self, nums: List[int]) -> int:
            dic = dict()
            # 边界
            dic[0] = 0
            res = 0
            zero, one = 0, 0
            for i in range(1, len(nums) + 1):
                x = nums[i - 1]
                if x == 0:
                    zero += 1
                else:
                    one += 1
                # 存在以i结尾的某个区间的1的数目减去0的数目的差值为0那么更新一下答案
                if one - zero in dic:
                    res = max(res, i - dic[one - zero])
                else:
                    # 存储最开始1的数目减去0的数目的位置i
                    dic[one - zero] = i
            return res