力扣-前缀和系列

523. 连续的子数组和 - 力扣（LeetCode）

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        if(nums.size() < 2) return false;
        unordered_map<int, int> mp;
        mp[0] = -1;
        if(nums[0] % k != 0)mp[nums[0] % k] = 0;
        for(int i = 1; i < nums.size(); i++){
            nums[i] += nums[i - 1];
            int m = nums[i] % k;
            if(!mp.count(m)) mp[m] = i;
            else if(mp.count(m) && i - mp[m] >= 2) return true;
        }
        return false;
    }
};

    前缀和的题目，不仅需要前缀和，还需要设置一个哈希表，这种需要算相同k的倍数的子数组，要考虑两个前缀和是否同余，如果同余那么之间的子数组就可以是k的倍数了。

525. 连续数组 - 力扣（LeetCode）

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        if(nums.size() < 2) return 0;
        vector<int> presum(nums.size() + 10, 0);
        unordered_map<float, int> m;

        for(int i = 1; i <= nums.size(); i++){
            presum[i] = presum[i-1] + nums[i - 1];
        }
        int ret = 0;
        for(int i = 0; i <= nums.size(); i++){
            float k = (float)presum[i] - (float)i/(float)2;
            if(!m.count(k))m[k] = i;
            else ret = max(ret, i - m[k]);
        }

        return ret;
    }
};

    这也是一道前缀和加哈希表的题目，很巧妙的一个方法

• 因为元素仅有0和1，所以子数组的元素和即为1的数量，子数组长度-元素和=0的数量
• 所以可以符合题意的子数组满足公式 preSum[ j ]-preSum[ i ]=( j - i )/2;
• 移项得：preSum[ i ]-i/2=preSum[ j ]-j/2，即 newNums[ i ]=newNums[ j ]; 此时容易想到哈希表计数，问题解决。具体实现可以优化成一次遍历。