## 题目描述：

LeetCode 525. 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.

## 解题思路：

```首先，将原始数组nums中的0替换为-1

如果m == 0，则ans = max(ans, i + 1)

否则，ans = max(ans, dmap[m] - i)```

## Python代码：

``````class Solution(object):
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
sums = [0] * len(nums)
dmap = collections.defaultdict(int)
last = 0
for i, n in enumerate(nums):
last += 2 * nums[i] - 1
sums[i] = last
dmap[last] = max(dmap[last], i)
ans = 0
for i, m in enumerate(sums):
if m == 0:
ans = max(ans, i + 1)
else:
ans = max(ans, dmap[m] - i)
return ans
``````

## Python代码：

``````class Solution(object):
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
dmap = {0 : -1}
ans = total = 0
for i, n in enumerate(nums):
total += 2 * nums[i] - 1
if total in dmap:
ans = max(ans, i - dmap[total])
else:
dmap[total] = i
return ans
``````

Pingbacks已关闭。