leetcode_560 和为K的子数组

1. 题意

求和为k的子数组的个数

2. 题解

2.1 暴力

依然是枚举子串的做法，不过这题竟然没有超时。

固定子串的起点，再不断在该串后面添加数，并计算和。

class Solution {
public:int subarraySum(vector<int>& nums, int k) {// two sum int i = 0;int n = nums.size();int ans = 0;for (int i = 0; i < n; ++i) {int tot = 0;for (int j = i; j < n; ++j) {tot += nums[j];if (tot == k)ans++;}}return ans;}
};

2.2 前缀和

对于子串和的问题， 我们都需要考虑能否用下前缀和。

对于本题目，如果使用前缀和的话；就变成了找到所有的
$pre[j]-pre[i]=k,i＜j$。

我们仔细一看$pre[j]+(-pre[i])=k$，这不就是两数之和变个形吗？

因此可以用哈希表进行优化。

还有需要注意的一点是对$pre[0]$的处理！

class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> cnts;int ans = 0;int cur = 0; for (int num: nums) {cnts[cur]++;cur += num;if (cnts.contains( cur - k)) {ans += cnts[cur - k];}}return ans;}
};