560. 和为 K 的子数组

滑动窗口

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        const int n = nums.size();
        vector<int> sum(n+1);
        for(int i = 0;i<n;++i){
            sum[i+1] = sum[i] + nums[i];
        }

        int l = 1;
        int r = 1;
        int result = 0;
        while(l<=n&&r<=n){
            int s = sum[r] - sum[l-1];
            if(s<k){
                r++;
            }else if(s>k){
                l++;
            }else{
                result++;
                l++;
            }
        }
        return result;
    }
};

过不了这个样例：

输入

nums =
[-1,-1,1]
k =
0

输出：

0

预期输出：

1

原因是滑动窗口适用于窗口内元素总和单调增加或者减少的时候，简单来说就是数组中只有正数或者只有负数的情况。而在这个例子中，数组中同时存在正数和负数，单调性被破坏了，因此滑动窗口不适用。

前缀和加哈希表

使用 sum[i]表示前 i 个元素的和，sum[j] - sum[i-1]表示[i,j]的子数组和。

假设 k = sum[j] - sum[i-1]，则有 sum[j] - k = sum[i-1]。

即看可以看 sum[i-1]的出现次数来求和为 k 的子数组个数。

需要注意的是，sum[0] 也要加到哈希表中，因为如果从 0 开始的子数组和为 k，那么 sum[j] - k = 0。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> mp;
        const int n = nums.size();
        vector<int> sum(n+1);
        mp[0] = 1;
        for(int i = 1;i<=n;++i){
            sum[i] = sum[i-1] + nums[i-1];
            mp[sum[i]] ++;
        }

        int result = 0;
        for(int i = 1;i<=n;++i){
            result += mp[sum[i]-k];
        }

        return result;
    }
};

仔细观察，因为只用到了 sum[i]，所以可以不开数组， 直接使用一个变量来存储前缀和。

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;

        int sum = 0;
        int result = 0;
        for (auto i : nums) {
            sum += i;
            result += mp[sum - k];
            mp[sum]++;
        }

        return result;
    }
};

这三条语句的顺序很重要

            sum += i;
            result += mp[sum - k];
            mp[sum]++;

假设我们运算到第 i 个元素，要求 sum[i] - k 的出现次数，所以先计算前缀和，再查找哈希表，sum[i] 存到 mp 要放在最后，因为可能有 k=0 的情况，如果我们提前存了 sum[i]，那么会有 sum[i] - k = sum[i]这种情况，相当于(i,i)这个子数组的和为 k，这个子数组的长度为 0，不符合题意。

还有这样写的：

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        int sum = 0;
        int result = 0;
        for (auto i : nums) {
            mp[sum]++;
            sum += i;
            result += mp[sum - k];
        }

        return result;
    }
};

删除了mp[0] = 1;，提前了mp[sum]++;，这样也可以通过测试用例。

原因是往 mp 中存 sum[n]没有意义，用不到。提前mp[0] = 1,也可以保证开始时 mp[0] = 1,并且每次存的都是上次循环的前缀和，所以也不会出错。