LeetCode 525. Contiguous Array

Posted on | In |
Words count in article: 227 | Reading time ≈ 1

题目

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

Example 1:

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

Example 2:

1
2
3
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.

思路

Using HashMap.
首先考虑如何计算具有相同数量的0和1，可以通过将0转换为-1(可以通过2*nums[i] -1的方法)，若长度n的元素之和为0，则说明n个元素中的0与1的个数相等。若前n个元素之和等于前n+j个元素之和，则n到n+j个元素中的0与1个数相等。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution(object):
    def findMaxLength(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        dic = {0: -1}
        res = s = 0
        for i, n in enumerate(nums):
            s += 2*n-1
            if s in dic:
                res = max(res, i-dic[s])
            else:
                dic[s] = i
        return res