【前缀和】和为 K 的子数组（medium）

题目描述

和为 K 的子数组

给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
示例 1：
输入:nums = [1,1,1], k = 2
输出: 2
解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2：
输入:nums = [1,2,3], k = 3
输出: 2
提示:
1 <= nums.length <= 2 * 10⁴
-1000 <= nums[i] <= 1000
-10⁷ <= k <= 10⁷

算法原理和细节问题

解法（将前缀和存在哈希表中）：
算法思路：
设 i 为数组中的任意位置，⽤ sum[i] 表⽰ [0, i] 区间内所有元素的和。
想知道有多少个「以 i 为结尾的和为 k 的⼦数组」，就要找到有多少个起始位置为 x1, x2, x3… 使得 [x, i] 区间内的所有元素的和为 k 。那么 [0, x] 区间内的和是不是就是sum[i] - k 了。于是问题就变成：
◦ 找到在 [0, i - 1] 区间内，有多少前缀和等于 sum[i] - k 的即可。
我们不⽤真的初始化⼀个前缀和数组，因为我们只关⼼在 i 位置之前，有多少个前缀和等于sum[i] - k 。因此，我们仅需⽤⼀个哈希表，⼀边求当前位置的前缀和，⼀边存下之前每⼀种前缀和出现的次数。

代码

C++ 算法代码：

class Solution
{
public:
 int subarraySum(vector<int>& nums, int k) 
 {
 unordered_map<int, int> hash; // 统计前缀和出现的次数
 hash[0] = 1;
 int sum = 0, ret = 0;
 for(auto x : nums)
 {
 sum += x; // 计算当前位置的前缀和
 if(hash.count(sum - k)) ret += hash[sum - k]; // 统计个数
 hash[sum]++;
 }
 return ret;
 }
}

Java 算法代码：

class Solution {
 public int subarraySum(int[] nums, int k) {
	 Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
	 hash.put(0, 1);
	 int sum = 0, ret = 0;
	 for(int x : nums){
		 sum += x; // 计算当前位置的前缀和
		 ret += hash.getOrDefault(sum - k, 0); // 统计结果
		 hash.put(sum, hash.getOrDefault(sum, 0) + 1); // 把当前的前缀和丢到哈希表⾥⾯
	 }
	 return ret;
 }
}

注：统计结果 和 把当前的前缀丢到哈希表里不能换顺序
否则k=0时将不会输出0