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），要求找到最长的子数组，使得该子数组中0和1的个数相等。 感觉应该用DP和累加和，但是没想出具体的解法，参考网上的题解。 把数组中的0换成-1，然后计算累加和，把[0,i]的累加和及对应的下标存入到一个hash中，即hash[sum[0,i]]=i，在后续的累加计算中，如果遇到累加和出现在hash中，则说明这两个区间之间的0和1个数相等。比如下面的例子：
- 序列： 1,-1,-1,-1,1,-1,-1,-1,1
- 累加和：1,0,-1,-2,-1,-2,-3,-4,-3
累加和第一次遇到-2时，记录hash[-2]=3，表示sum[0,3]=-2，当再次遇到累加和为-2时，是sum[0,5]=-2，则说明[4,5]之间的1和-1个数是相等的。因为序列中没有0元素，两次的累加和又一样，说明中间经过的数累加和是0，导致累加和没变化，累加和是0，又说明1和-1的个数相等，即1和0的个数相等。
代码如下，初始时，没有元素，累加和也是0，但是要记录下标是-1，实际跑一下第一个样例就知道了。
class Solution {
public:
int findMaxLength(vector<int>& nums)
{
unordered_map<int, int> hash;
hash[0] = -1; // init
int sum = 0, n = nums.size(), ans = 0;
for (int i = 0; i < n; ++i) {
sum += nums[i] == 1 ? 1 : -1;
if (hash.find(sum) != hash.end()) {
ans = max(ans, i – hash[sum]);
}
else {
hash[sum] = i;
}
}
return ans;
}
};本代码提交AC，用时138MS。
果然遇到子数组的问题，要善于利用累加和/积的方法。