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.
解題思路：
遍歷數(shù)組，記錄當(dāng)前下標(biāo) i 下1比0多的個(gè)數(shù)立美，記為diff,如果不在哈希表中次坡，則將<diff,i>存入哈希表中掸刊，如果存在于哈希表中猜嘱，則hash[diff]和i之間的1和0的個(gè)數(shù)相等勇劣，則直接更新最長(zhǎng)的長(zhǎng)度功咒。代碼如下：
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]的情況下，當(dāng)i為1時(shí)氮发，diff = 0, 這時(shí)候應(yīng)該要更新maxLen,所以渴肉，hash[0]應(yīng)該初始化為-1.
相關(guān)習(xí)題：
523. Continuous Subarray Sum
