LeetCode 525. Contiguous Array

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.

Approach

题目大意：给你一组数据，问你连续子串中0和1的数量相等的最大长度
思路方法：我们将0改成-1，这样用hashmap记录连续和sum，如果sum已被记录（说明这段长度中和为0），则计算长度。

Code

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