560. 和为 K 的子数组

刷题记录
留言

560. 和为 K 的子数组

题目

给你一个整数数组 nums 和一个整数 k ，请你统计并返回该数组中和为 k 的连续子数组的个数。

示例 1：

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

示例 2：

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

提示：

  • $1 <= nums.length <= 2 * 10^4$
  • -1000 <= nums[i] <= 1000

主要思路

这道题最开始挺容易想到滑动窗口，但其实并不适用，因为可能存在负值。

正确的做法是前缀和+hash

前缀和表示的是从0-i的数之和，则我们计算连续数组i-j的和是否为$k$可以利用公式$pre[i]-pre[j-1]$来计算，也就可以转换成$pre[j-1]=pre[i]-k$.

我们使用hash表统计和$pre[i]-k$相同的$pre[j]$的个数（和为键，次数为值），利用hash表来避免二次遍历找剩余和。

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int subarraySum(vector<int>& nums, int k) {
        unordered_map<int,int> hash;
        // 前缀和pre[i]表示从nums[0]~nums[i]的和，更新只和前一个数有关，所以可以优化为一个变量
        int count=0,pre=0;
        // 应对0-i相加的和正好为k的情况
        hash[0]=1;
        for(auto num:nums){
            pre += num;
            if(hash.find(pre-k)!=hash.end()){
                count+=hash[pre-k];
            }
            hash[pre]++;
        }
        return count;
    }
};