Table of Contents
中等给你一个整数数组
nums和一个整数k，请你统计并返回 该数组中和为k的子数组的个数 。子数组是数组中元素的连续非空序列。
示例 1：
示例 2：
提示：
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
前排提示：由于数组 nums 不单调且存在负数，不适合用滑动窗口来做。
本题是连续子数组和问题，可以用前缀和转化。因此想要解决这道题，需要先理解如何使用前缀和转化问题，这就要先来看看前缀和模板题了。
前缀和模板题
这里有一道整数数组前缀和模板题，可以帮助我们很好地理解前缀和。
下面用 a 来代指数组 nums
这道题需要我们设计一个类型 NumArray，实现它的初始化函数 Constructor 和一个用来求 a[i] ~ a[j] 的元素和的 SumRange 方法，。
关键思路
这里有一个数组 a = [1, 2, 3, 4, 5, 6]，要想计算子数组 [3, 4, 5] 的元素和，可以用前缀 [1, 2, 3, 4, 5] 的元素和 减去前缀 [1, 2] 的元素和。即:
3+4+5 = (1+2+3+4+5) - (1+2)相当于前缀 [1, 2, 3, 4, 5] 去掉前缀 [1, 2] 就得到了子数组 [3, 4, 5]
一般地，任意子数组都是一个前缀去掉前缀后的结果。所以任意子数组的和，都可以表示为两个前缀和的差。
a 的子数组有 O(n^2) 个 （n*(n+1)/2），但只有 O(n) 个前缀。那么预处理 a 的所有前缀和，就可以 O(1) 计算任意子数组的元素和。
具体思路
nums 记作 a，其长度为n
对于数组 a ，计算它的长为 n+1 的前缀和数组 s，即计算 「a 的前 0 个数的和」， 「前 1 个数的和」，「前 2 个数的和」 …… 「前 n 个数的和」，这些和组成一个数组 s。
// 注意这里 s[0] = 0s[0] = 0s[1] = a[0]s[2] = a[0] + a[1] ⋮s[i] = a[0] + a[1] + ⋯ + a[i−1]s[i+1] =a[0] + a[1] + ⋯ + a[i−1] + a[i] ⋮s[n] = a[0] + a[1] + ⋯ + a[n−1]通过前缀和，我们可以把子数组的元素和 转化成两个前缀和的差。
下标区间 [left, right] 的元素和 等于前缀 [0, right] 的元素和 减去 [0, left-1] 的元素和，即
s[right+1] - s[left]示例数组 [−2,0,3,−5,2,−1]
对应的前缀和数组 s = [0,−2,−2,1,−4,−2,−3]
需要求子数组 [3,−5,2,−1] 的和
有了这个式子，我们就可以 O(1) 计算出：s[6] - s[2] = -3 -(-2) = -1
为什么要定义 s[0] = 0，这样做有什么好处
当 left == 0 时，要计算的子数组其实是一个前缀（从 a[0] 到 a[right] ）。
如果不定义 s[0] = 0
- 无法只用一个公式
s[i] = s[i-1] + x来计算前缀和，此时需要特判 i = 0 的情况了。 - 同时计算差值时
s[right] - s[left-1]也需要对 left = 0 进行特判。
通过定义 s[0] = 0, 任意子数组（包括前缀）都可以表示为两个前缀和的差 s[right+1] - s[left]。
此外，如果 a 是空数组，定义 s[0] = 0 可以兼容这种情况，体现在计算前缀和数组 s ：
如果不定义 s[0] = 0，那么当遇到空数组时，s 也会是空数组，需要对空数组的情况进行特判。
这里有点像链表章节题目里常用的虚拟头结点，通过添加虚拟头结点，统一对链表各元素的操作。
另外一种涉及到子数组的时候，前缀和为什么要添加0的解释：
对于范围 [i, j]子数组而言，其和为： s[j] - s[i - 1]
类似于动态规划，为了避免i - 1是负数，我们可以选择把表达式改为： s[j + 1] - s[i] 并在最前面添加一个状态0
代码实现
type NumArray []int
// 构造前缀和数组func Constructor(nums []int) NumArray { s := make(NumArray, len(nums)+1) for i, x := range nums { s[i+1] = s[i] +x } return s}
// 计算区间内前缀和func (s NumArray) SumRange(left int, right int) int { return s[right+1] - s[left]}
/** * Your NumArray object will be instantiated and called as such: * obj := Constructor(nums); * param_1 := obj.SumRange(left,right); */560. 和为 K 的子数组 题解
关键思路
求整数数组 nums 中和为 k 的子数组的个数（子数组是数组中元素的连续非空序列）。
根据 303 题的前缀和的定义：
nums 是一个长度为 n 的数组。
s 是 nums 的前缀和数字，长为 n+1，第一项 s[0] 设为0，最后一项的下标为 n。
s[0] = 0s[i] = nums[0] + nums[1] + ⋯ + nums[i-1]设 i < j，如果 nums[i] 到 nums[j-1] 的元素和等于 k ，用前缀和表示：
s[j] - s[i] = k问题转化为：
- s 中有多少对下标 (i, j) 满足 0≤i<j≤n 且 s[j] - s[i] = k
即 s[j] + (-s[i]) = k，转化为了两数之和的问题。只不过两数之和只需找到一对下标，本题需要计算所有满足条件的下标对的个数。
如果用二重循环暴力枚举满足的下标对，时间复杂度是 O(n^2)。如何加速？
可以根据两数之和的思路， s[j] - s[i] = k 移项得
s[i] = s[j] - k代码实现
func subarraySum(nums []int, k int) int { s := make([]int, len(nums)+1) // 前缀和数组 for i, x := range nums { // 计算前缀和 s[i+1] = s[i] + x // s[0] == 0 } // 设 i < j，求 nums[i] 到 nums[j-1] 的元素和等于k // 用前缀和表示： s[j] - s[i] == k (两数之和) // s[i] == s[j] - k cnt := make(map[int]int, len(s)) ans := 0 for _, sj := range s { // 遍历 s[j] 的时候顺便把出现过的元素（即需要判断的元素s[i] ）存入哈希表了 ans += cnt[sj-k] // 寻找有没有符合条件是 s[i]，如果有计数+1 cnt[sj]++ } return ans}遍历 s[j] 的时候顺便把出现过的元素（即需要判断的元素s[i] ）存入哈希表了。相当两次遍历，先遍历了一遍 s[j]，又遍历一遍 s[i]，只不过是把 s[i] 存入哈希表，使遍历时间复杂度降为了 O(1).
答疑
问：为什么这样做可以不重不漏地计算？
答：暴力做法是，外层循环枚举 j，内层循环枚举 i，如果 s[j]−s[i]=k，那么答案加一。我们保留了「外层循环枚举 j」这个过程，把内层循环用哈希表优化成了 O(1)，所以本质是对暴力算法的哈希表优化。既然暴力算法是不重不漏地计算，那么优化做法也是不重不漏地计算。
问：为什么要把 s[0]=0 也加到哈希表中？
答：举个最简单的例子，nums=[1], k=1。如果不把 s[0]=0 加到哈希表中，按照我们的算法，没法算出这里有 1 个符合要求的子数组。也可以这样理解，要想把任意子数组都表示成两个前缀和的差，必须添加 s[0]=0，否则当子数组是前缀时，没法减去一个数，具体见 前缀和及其扩展 中的讲解。
问：为什么代码中要先更新 ans，再更新 cnt？这两行代码能否交换？
答：不行，这会在 k=0 的时候算错。例如 nums=[2], k=0，正确答案应该是 0，但如果先把 cnt[2] 加一，再把 cnt[2] 加到 ans 中，最后返回的 ans 就不是 0 了。
问：为什么这题不适合用滑动窗口做？
答：滑动窗口需要满足单调性，当右端点元素进入窗口时，窗口元素和是不能减少的。本题 nums 包含负数，当负数进入窗口时，窗口左端点该往哪个方向移动？无法确定。如果没有负数的话，则可以用滑动窗口（恰好型滑动窗口），见 930. 和相同的二元子数组。
