# 525. Contiguous Array 连续数组

@TOC

## # 题目描述

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

## # 解题方法

### # 累积和

python代码如下：

``````class Solution:
def findMaxLength(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
print(nums)
total_sum = 0
index_map = dict()
index_map[0] = -1
res = 0
for i, num in enumerate(nums):
if num == 0:
total_sum -= 1
else:
total_sum += 1
if total_sum in index_map:
res = max(res, i - index_map[total_sum])
else:
index_map[total_sum] = i
return res
``````

C++代码如下：

``````class Solution {
public:
int findMaxLength(vector<int>& nums) {
const int N = nums.size();
unordered_map<int, int> m_;
for (int& num : nums) {
if (num == 0) {
num = -1;
}
}
m_.insert({0, -1});
int sums = 0;
int res = 0;
for (int i = 0; i < N; ++i) {
sums += nums[i];
if (m_.count(sums)) {
res = max(res, i - m_[sums]);
}
m_.insert({sums, i});
}
}
return res;
}
};
``````

https://leetcode.com/problems/contiguous-array/discuss/99646/Easy-Java-O(n)-Solution-PreSum-+-HashMap https://leetcode.com/articles/contiguous-array/

## # 日期

2018 年 9 月 12 日 ———— 做题还是要有耐心