525. Contiguous Array（week6）
题目描述
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.
解题思路
一眼看上去，是一道非常简单的题目。题目要求我们找出0和1数量相同的最长子串。通俗点考虑，我们从数组的每一个元素开始遍历一次整个数组，就可以找出最长的子串，时间复杂度是O(n^2) 。然而，这时，由于题目给出的数组大小会达到50000——虽然并不是一个很大的数量级，但在n^2之后还是能到达十亿以上的计算复杂度。因此这种暴力算法在这道题显然是不能奏效的。
那么，我们再次观察一下这个字符集：都是0和1组成。或者说是由两个不同的字符组成的，如果题目将0换成别的数字，也不会影响最后的输出。这时，我们将0换成1的相反数——-1会如何呢？
由于-1+1=0，所以，符合条件的串肯定满足串内元素之和为0。我们设一个sum数组，里面记录着从0到index（下标）的数字之和，若sum[a] == sum[b]，那么从a-b拿到的串就一定是符合要求的0和1数量相同的串。
但这样同样也有一个问题：当我们遍历到下标a时，我们要找之前与它有相同值的sum，在数组这种数据结构的基础上并不好实现，查找复杂度将会到达O(a)的量级，这样，最后的复杂度还是会回到O(n^2)。因此，这个sum的查找复杂度应该要下降到O(1)或者O(loga)。每到这种需要降低查找复杂度的时候，我们都会想到它：Map。利用哈希表，查找复杂度最低可达O(1)最高也不过是O(logn)。
这样，这道题目就算是解决了。emmmm，似乎还是比较简单。
空间复杂度分析
哈希表O(n)
时间复杂度分析
循环算出每个下标的sum，需要O(n)，查找复杂度O(1)。总复杂度O(n)。
源码
#define max(a,b) a >= b ? a : b
class Solution {
public:
int findMaxLength(vector<int>& nums) {
map<int, int> sumMap;
int maxLength = 0, sum = 0;
map[0] = -1;
for (int i = 0; i < nums.size(); ++i) {
sum += (nums[i] == 0) ? -1 : 1;
if (sumMap.find(sum) != sumMap.end()) {
maxLength = max(maxLength, i - sumMap[sum]);
} else {
sumMap[sum] = i;
}
}
return maxLength;
}
};
