https://leetcode.com/problems/contiguous-array/
Medium
问题描述：
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
题目分析：
题目给定了一个由0和1构成的数组，我们需要从这个数组中找出一个长度最长、同时0和1个数相同的子数组。
这一题可以从求数组和入手，我们可以进行一次遍历，在遍历过程中，遇到0则加一，遇到1则减一。
以[0, 1, 0, 1, 1]为例，我们设置三个变量：count代表当前位置记录值，count_dict是一个字典，对应关系是count值:该count值对应位置，初始化为{0:0}，max_length记录当前最大子序列长度。
1
2
3
4
5
6
| max_length = max(index - count, max_length)
index:1, num:0, count:1, max_length:0, count_dict:{0: 0, 1: 1}
index:2, num:1, count:0, max_length:2, count_dict:{0: 0, 1: 1}
index:3, num:0, count:1, max_length:2, count_dict:{0: 0, 1: 1}
index:4, num:1, count:0, max_length:4, count_dict:{0: 0, 1: 1}
index:5, num:1, count:-1, max_length:4, count_dict:{0: 0, 1: 1, -1: 5}
|
需要注意的是，index需要从1开始，这是由于字典初始化包含了key=0，因此需要从1开始。
代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution(object):
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
if len(nums) == 0 or len(nums) == 1:
return 0
count = 0
count_dict = {0: 0}
max_length = 0
for i in range(1, len(nums) + 1):
if nums[i - 1] == 0:
count += 1
else:
count -= 1
if count in count_dict:
max_length = max(max_length, i - count_dict[count])
else:
count_dict[count] = i
return max_length
|