首页 🍒LeetCode,🐶算法

题目

KNbvwqIHFz.png

思路

和上一个前缀和的题思路差不多,也是把前缀和都求出来然后pre[i] - pre[j]就是i~j子数组的和。

子数组中0和1的数量相同说明当前子数组的和num * 2 == i - j
也就是(pre[i] - pre[j]) * 2 == i - j

如果直接用上面的式子两层遍历会超时,所以还得优化。
上面的式子移项可得pre[i] * 2 - i == pre[j] * 2 - j
这样每一项就只和自己有关就不用两层循环了,用map把pre[i] * 2 - i存起来,然后比较每个相同的值即可。

还有一种情况是从范围为0~i,利用前缀和求j~i区间的和应该是pre[i] - pre[j - 1]
所以如果范围是0~i,数组范围不能是-1,所以这种情况就应该只判断pre[i] * 2 == i + 1等于则符合条件

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        int n = nums.size(), nmax = 0;
        map<int, int> mp;
        vector<int> pre(n, 0);
        pre[0] = nums[0];
        for (int i = 1; i < n; i++) {
            pre[i] = pre[i - 1] + nums[i];
        }
        // (pre[i] - pre[j]) * 2 == i - j
        for (int i = 0; i < n; i++) {
            int m = pre[i] * 2 - i;
            if (pre[i] * 2 == i + 1) nmax =max(i + 1, nmax);
            else if (mp.count(m)) nmax =max(i - mp[m], nmax);
            else mp[m] = i;
        }
        return nmax;
    }
};



文章评论

    六天 访客ChromeWindows
    11天 前   回复

    好耶