Leetcode 525: Contiguous Array

https://leetcode.com/problems/contiguous-array/description/

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.

Notes:

This is another classic question about the subarray (or continuous subarray).

For these kinds of question, it seems always have O(N) or O(NlogN) solutions. And the brute force solution is O(N^2).

To this question, the only trick part is how to count 0 and 1?

One way to do this is using a counting variable. When meets with 1, ++count; when 0, --count. When the same count value appears,  the subarray between them should have equal number of 0 and 1.

See the code below:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int res = 0, sum = 0;
        unordered_map<int, int> mp;
        mp[0] = -1;
        for(int i=0; i<nums.size(); ++i) {
            if(nums[i]) ++sum;
            else --sum;
            if(mp.count(sum)) res = max(res, i - mp[sum]);
            else mp[sum] = i;
        }
        return res;
    }
};
auto gucciGang = []() {std::ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();