leetcode – 525. Contiguous Array

Description

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

Example 1:

Input: nums = [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray wi服务器托管网th an equal number of 0 and 1.

Example 2:

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

Constraints:

1 

Solution

Prefix sum, use the difference between the count of 1s and 0s as the key, and the first index as the value. If two differences are the same, then all the subarray in between is a valid subarray.

Time complexity:

o

(

n

)

o(n)

o(n)
Space complexity:

o

(

n

)

o(n)

o(n)

Code

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        # {diff between 0s and 1s: index}
        pre_sum = {0: -1}
        cur_sum = 0
        res = 0
        for i, each_num in enumerate(nums):
           服务器托管网 if each_num & 1 == 1:
                cur_sum += 1
            else:
                cur_sum -= 1
            if cur_sum not in pre_sum:
                pre_sum[cur_sum] = i
            else:
                res = max(res, i - pre_sum[cur_sum])
        return res

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: Python和Java的区别（不断更新）

主要通过几个方面区分Python和Java，让大家有一个对比： 语言类型 Java是一种静态类型、编译型语言。 Python是一种动态类型、解释型语言，注重简洁和灵活的语法。 语法 在Java中，变量需要显式地声明，指定其类型。例如： int length=1…