0525：连续数组（★）

2016-06-08 约 333 字预计阅读 1 分钟次阅读

力扣第 525 题

题目

给定一个二进制数组 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⁵
nums[i] 不是 0 就是 1

相似问题：

分析

假如将 0 都替换为 -1，那么就是找和为 0 的子数组
子数组的和容易想到前缀，问题转为求相等的前缀和的最长距离，用哈希表即可

解答

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12


class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        d = {0:-1}
        s = 0
        res = 0
        for i,x in enumerate(nums):
            s += 1 if x else -1
            if s in d:
                res = max(res,i-d[s])
            else:
                d[s] = i
        return res

145 ms

目录

0525：连续数组（★）

题目

分析

解答