525. Contiguous Array解题报告

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/

解题方法：

遍历数组，记录当前位置之前出现了多少个1（0被视为出现了-1个1），用哈希表存下来出现1的次数和对应的index，如果出现两个相同的次数，那么这中间的一段被视为我们所求的subarray。
注意：当哈希表里面已经存在的键值对再次出现，不需要更新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;
}