前缀和

LeetCode ：560. 和为 K 的子数组 - 力扣（LeetCode）

题解：（官方的更简洁，这里用官方的）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int, int> mp;
        mp[0] = 1;
        int count = 0, pre = 0;
        for (auto& x:nums) {
            pre += x;
            if (mp.find(pre - k) != mp.end()) {
                count += mp[pre - k];
            }
            mp[pre]++;
        }
        return count;
    }
};

这道题目的要求是：获取到一个数组中的连续的子数组和为给定值

原本我们要找的是
$$
nums[i]+…+nums[i+j]=k
$$
这么一串值，那么是否可以转化一下：

将 mp 设定为前缀和,两边同时加上前缀和
$$
mp[i]+nums[i]+…+nums[i+j]= mp[i]+k
$$
化简为：
$$
mp[i+j]= mp[i]+ k
$$
那这样就可以通过前缀和来获取连续子数组的位置了

通过在查询哈希表中是否有 mp[i]+k 就可以知道是否存在这个子数组

这里说明一下，上述题目不能使用滑动窗口，因为有负值并且不是最小的连续子数组

比如可以是[-1,1,1,-1] 在要求和为 0 时,滑动窗口并不好写