[leetcode] 525. Contiguous Array

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.

相关习题：
523. Continuous Subarray Sum

转载于:https://www.jianshu.com/p/818ce8f6fa1c