Description

给定二进制数组$a$，返回最长的0和1数目相同的子数组长度

Constraints

$1\le a.length\le {10}^5$

Solution

用表记录一下前缀和即可

前缀和指的是$\{0\to -1,1\to 1\}$，这样和为$0$就代表0和1数目相同

每个相同的前缀和只取第一次，作差就能得到当前最长的情况

Code

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        // {presum, index}
        std::unordered_map<int, int> rec;
        int len = 0, sum = 0;
        rec[0] = -1; // Note
        for(int i = 0; i < nums.size(); ++i) {
            int v = nums[i];
            sum += (v ? 1 : -1);
            if(rec.count(sum)) len = std::max(len, i - rec[sum]);
            else rec[sum] = i;
        }
        return len;
    }
};

Link

LeetCode-525 Contiguous Array