Description:

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example:

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.

Link:

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

解題方法：

遍歷數(shù)組，記錄當(dāng)前位置之前出現(xiàn)了多少個(gè)1（0被視為出現(xiàn)了-1個(gè)1），用哈希表存下來出現(xiàn)1的次數(shù)和對(duì)應(yīng)的index，如果出現(xiàn)兩個(gè)相同的次數(shù)，那么這中間的一段被視為我們所求的subarray。
注意：當(dāng)哈希表里面已經(jīng)存在的鍵值對(duì)再次出現(xiàn)，不需要更新index的值。

Tips:

Time Complexity：

O(N)

完整代碼：

int findMaxLength(vector<int>& nums) {
    int len = nums.size();
    if(!len)
        return 0;
    unordered_map<int, int> hash;
    hash[0] = 0;
    int last = 0;
    int ones = 0;
    int result = 0;
    for(int i = 0; i <= len; i++) {
        ones += last;
        if(hash.find(ones) != hash.end()) {
            result = max(result, i - hash[ones]);
        }
        else {
            hash[ones] = i;
        }
        if(i == len)
            break;
        else {
            last = nums[i] == 0 ? -1 : 1;
        }
    }
    return result;
}