题目浅析

  • 想查看原题可以点击题目链接。

  • 简单地说，就是给一个由 0 和 1 组成的数组，求其中 0 与 1 数量相同的长度最长的子数组的长度。

思路分享

  • 前缀和的思路，可以参考 【Leetcode Daily】303区域和检索-数组不可变

  • 如何衡量子数组中的 0 和 1 数量相同呢？有一种方便的方法，就是把 0 视作 -1，这样子数组的和为 0 的话就算是满足条件的子数组了。（发现变着花样地凑子数组和为零算是这种类型题的常见套路了）

  • 那么接下来，只要用哈希表记录前缀和对应的最左下标，一旦发现之前记录过相同数值的前缀和，就可以记录现在下标与记录下标之差作为结果参照之一。

  • 注意，这种一般都要设置一个初始值，比如本题下面的参考解法就是给数值零设置初始值 -1，原因是哈希表的意义是每个前缀和数值对应的最左下标的前一位，所以对于从第一位就可能是子数组的情况而言，需要往前算一位。比如 [0, 1]，遍历到 1，此时下标为 1，也算满足条件的子数组，此时如果哈希表中对应 0 的数值为 0，计算出来的长度就是 1 的错误答案。

代码解答（强烈建议自行解答后再看）

  • 参考题解
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        rec = defaultdict(int)
        rec[0] = -1
        ans = 0
        pre = 0
        
        for i, x in enumerate(nums):
            pre += 1 if x == 1 else -1
            if pre in rec:
                ans = max(ans, i - rec[pre])
            else:
                rec[pre] = i
        
        return ans