LeetCode-525 连续数组

Table of Contents

LeetCode-525 连续数组 #

Solution 1 #

把 $0$ 修改成 $-1$, 寻找和为 $0$ 的最长子数组, 用前缀和 + 哈希来处理. 注意初始化 $book[0] = -1$.

代码如下:

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