题目
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。
子数组是数组中元素的连续非空序列。
示例 1：
输入：nums = [1,1,1], k = 2 输出：2
示例 2：
输入：nums = [1,2,3], k = 3 输出：2
提示：
-
1 <= nums.length <= 2 * 104 -
-1000 <= nums[i] <= 1000 -
-107 <= k <= 107
思路
这道题我第一想法是滑动窗口，后面发现滑动窗口适合求那种窗口一直滑然后找极致的题目，这里显然不是，它要所有可能，然后我就往动态规划和前后缀方向靠，发现前缀和好像能做，而且能在O(n)内做出来
C++代码如下：
class Solution {
public:int subarraySum(vector<int>& nums, int k) {unordered_map<int,int> map = {{0,1}}; //0的情况也有一个，也得算进去int sum = 0,ans = 0;for(auto& num:nums){sum += num;int cur = sum - k;if(map.count(cur)){ans += map[cur];}map[sum] += 1;}return ans;}
};python代码如下：
class Solution(object):def subarraySum(self, nums, k):map = {0:1}ans,sum = 0,0for(num:nums):sum += numans += map.get(sum-k,0)map[sum] = map.get(sum,0)+1return ans也可以使用defaultdict
class Solution(object):def subarraySum(self, nums, k):map = defaultdict(int)map[0] = 1ans,sum = 0,0for(num:nums):sum += numans += map[sum-k]map[sum] += 1return ans
