【LeetCode刷题记录】560. 和为 K 的子数组

560 和为 K 的子数组

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。

示例 1：
输入：nums = [1,1,1], k = 2
输出：2

示例 2：
输入：nums = [1,2,3], k = 3
输出：2

提示：
$1<=nums.length<=2\ast 10^4$
$-1000<=nums[i]<=1000$
$-10^7<=k<=10^7$

思路

本题采用前缀和+哈希表的思想。（参考力扣官方题解）
假设第i个前缀和为sum[i]，要找到连续子序列和为k的序列，则需要判断到sum[i]-k的前缀和sum[j]是否存在，存在则等于k的子序列即为 $j+1,\dots \dots ,i$。可采用map存储键值对，其中键为每个元素的前缀和，值为该前缀和出现次数。

需要注意的是：

• map的第一项m[0]需要初始化为1，代表当前元素的前缀和恰好为k
• 统计前缀和出现次数需要放在找前缀和sum[i]-k之后，因为是找在m[sum]之前的前缀和有没有符合条件的
• cnt加上之前所有出现过的前缀和的次数，是考虑到负数和0的情况，他们会使前缀和不发生变化，但也是一种排列情况。
  比如[1,-1,0],k=0,每个元素的前缀和是[1,0,0],
  i=0, sum[i]-k=1, m[1]=0, cnt=0, m[1]=1
  i=1, sum[i]-k=0, m[0]=1, cnt=1, m[0]=2
  i=2, sum[i]-k=0, m[0]=2, cnt=1+2=3, m[0]=3
  故结果为3

代码

class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        int cnt = 0;
        // 前缀和为键，出现次数为对应值
        map<int, int> m;
        int sum = 0;
        // 将m[0]初始化为1，代表当前元素前缀和恰好等于k的情况
        m[0] = 1;
        for (int i = 0; i < nums.size(); i++) {
            sum += nums[i];
            if (m[sum - k] != 0) {
                // 考虑负数和0的情况，因为加上0对前缀和无影响
                // 故需要加上之前所有出现过的前缀和的次数
                cnt += m[sum - k];
            }
            // 统计前缀和出现的次数要放在找m[sum-k]之后，
            // 因为是找在m[sum]之前的前缀和有没有符合条件的
            m[sum]++;
        }
        return cnt;
    }
};