525. Contiguous Array

https://leetcode.com/problems/contiguous-array/

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

Thoughts

只由0和1组成的数组，问最长的满足相同数目0和1的子数组的长度。最优 + 子数组 => DP or 窗口 or presum。窗口要满足以i为底时，找到当前满足条件最长子数组的左边界l后，对i+1左边界l不再需要往回移动，但比如0011，当遇到第一个1时满足最长条件l会前移到第二个0，错误。如果把0看成-1，相同数目-1和1意味着子数组的和为0，因此找相同前缀和 => presum。又因为要找最长的，presum记录每次新前缀和出现第一次时所在位置。

Code

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

Analysis

时空都是O(n)