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.

Note: The length of the given binary array will not exceed 50,000.

利用hashmap紀錄preSum和index的關係，然後利用一個sum變數每看到一個1就加1，看到0就減1。因為要找長的，所以如果當前這個sum已經在mp的key裡了，那就不需要更新。

int findMaxLength(vector<int>& nums) { // time: O(n); space: O(n)
    unordered_map<int, int> mp; // preSum -> index
    mp[0] = -1; // initialization
    int res = 0, sum = 0;
    for (int i = 0; i < nums.size(); ++i) {
        sum += (nums[i] == 1) ? 1 : -1;
        if (mp.count(sum)) {
            res = max(res, i - mp[sum]);
        } else {
            mp[sum] = i;
        }
    }
    return res;
}

325. Maximum Size Subarray Sum Equals k