leetcode525-- 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.




class Solution(object):
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""

dic = {}
summ = 0
ret = 0

for i in range(len(nums)):

if nums[i]:
summ += 1
else:
summ -= 1

if summ ==0:
ret = max(ret, i+1)

if summ in dic:
ret = max(ret, i-dic[summ])
else:
dic[summ] = i

return ret





dic = {}
dic[0] = -1

summ = 0
ret = 0

for i in range(len(nums)):

if nums[i]:
summ += 1
else:
summ -= 1

if summ in dic:
ret = max(ret, i-dic[summ])
else:
dic[summ] = i

return ret




class Solution:
def findMaxLength(self, nums: List[int]) -> int:
summ = 0
ret = 0

dic = {}  # 用来存储当前N项和的index.方便后面找到和一样的段。
for i in range(len(nums)):
if nums[i]:
summ += 1
else:
summ -= 1

if summ == 0:    # 说明这时候从开始到现在这个地方刚好是满足的.
ret = max(ret, i+1)

if summ in dic:  # 即有两段的前n项和是一样的，那说明中间的这一段的0和1是一样的.
ret = max(ret, i - dic[summ])

else:
dic[summ] = i

return ret