Leetcode 525 Contiguous Array

发表于 |

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组。

示例 1:
输入: [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:
输入: [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。

注意: 给定的二进制数组的长度不会超过50000。

不想做重复的工作，这道题和523 560一模一样，如果你想弄懂前缀和的这个解法，建议先看560，再看523，我在另外两篇博客中写得很详细了
具体见https://buptwc.github.io/2018/07/10/Leetcode-523-Continuous-Subarray-Sum/

当你看懂前两道题后再来分析这道题，将所有的0变成-1，这道题就变成找最长的和为0的连续子数组，前缀和可解

思路：
（建议先看560，否则你可能不知道我在说什么）

  1. 改用字典存储已经遍历过的值，对应相应的下标，即d[sum(nums[:i])] = i，相同的key值取最小（最左边）的下标
  2. 依次遍历判断，若成功找到key值，存储一次长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        for i in range(len(nums)):
            if nums[i] == 0: nums[i] = -1
        sm = 0
        d = collections.defaultdict(lambda: float('inf'))
        d[0] = -1
        res = 0
        for i in range(len(nums)):
            sm += nums[i]
            if sm in d: 
                res = max(res,i-d[sm])
            d[sm] = min(d[sm],i) 
        return res


555 / 555 test cases passed.
difficulty: medium
Runtime: 292 ms,beats 91.27%
# 可以稍微优化一下，第一次的遍历nums将0改成1可以去除，直接在sm += nums[i]时判断nums[i]的值即可