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.
解题思路：
遍历数组，记录当前下标 i 下1比0多的个数，记为diff,如果不在哈希表中，则将<diff,i>存入哈希表中，如果存在于哈希表中，则hash[diff]和i之间的1和0的个数相等，则直接更新最长的长度。代码如下：
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int,int> hash;
int maxLen = 0, diff = 0;
hash[0] = -1; //这里hash[0]必须初始化
for(int i = 0; i < nums.size(); ++i)
{
diff += nums[i] == 1 ? 1 : -1;
if(hash.find(diff) != hash.end())
{
maxLen = max(maxLen, i - hash[diff]);
}else
{
hash[diff] = i;
}
}
return maxLen;
}
};
注意，代码中hash[0]必须初始化，在输入为[0,1]的情况下，当i为1时，diff = 0, 这时候应该要更新maxLen,所以，hash[0]应该初始化为-1.
