[LeetCode] 525. Contiguous Array

https://leetcode.com/contest/leetcode-weekly-contest-20/problems/contiguous-array/

Solution:
The straightforward way is of O(n2) time complexity, which is not what the OJ wants. There are only two elements in the vectors: 0 and 1. So we can define one variable to record the number difference of 0 and 1: sum. When it is 0, --sum; and when it is 1, ++sum. A hashmap is needed to connect the sum to the current position from which we can calculate the length of the subarray with the same number of 0 and 1. Then we need find the one with the maximum length.

In short, we will use map[sum] = i to record the position of i when the difference of the 0's and 1's number is sum. When the same sum appears again, let's say at position of j, then the subarray between i and j must contain the same number of 0 and 1.

Further thinking: how about there are three different elements in the array, and ask for the maximum subarray with the same number of each of them?

Code:

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int res = 0, sum = 0, n = nums.size();
        unordered_map<int, int> m;
        m[0] = 0;
        for(int i=0; i<n; ++i){
            if(nums[i] == 0) --sum;
            else ++sum;
            if(m.find(sum) != m.end()) res = max(res, i+1-m[sum]);
            else m[sum] = i+1;
        }
        return res;
    }
};