LeetCode525(2021.6.3)

LC525. 连续数组

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size();
        vector<int> s(n + 1);
        for (int i = 1; i <= n; ++i) s[i] = s[i - 1] + (nums[i - 1] ? 1 : -1);
        int res = 0;
        unordered_map<int, int> mp;
        mp[0] = 0;
        for (int i = 2; i <= n; ++i) {
            if(!mp.count(s[i - 2])) mp[s[i - 2]] = i - 2;
            if(mp.count(s[i])) res = max(res, i - mp[s[i]]);
        }
        return res;
    }
};

发表评论