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

前缀和

前缀和：nums 的第 0 项到当前项的和。

定义 prefixSum 数组，prefixSum[x]：第 0 项到第 x 项的和。

nums 的第 i 到 j 项的和，即为 prefixSum[j] − prefixSum[i−1]

当 i 为 0，此时 i-1 为 -1，我们故意让 prefixSum[-1] 为 0，使得通式在 i=0 时也成立

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
// 前缀和
func subarraySum(nums []int, k int) int {
	count := 0
	curSum := 0 // 记录每次循环当前的前缀和
	hash := map[int]int{
		0: 1, // 前缀和为0 出现过1次了
	}
	for i := 0; i < len(nums); i++ {
		curSum += nums[i]
		if hash[curSum-k] > 0 {
			// 当前前缀和减去k的结果也在之前的前缀和表中 代表找到一个和为k的连续子数组
			count += hash[curSum-k]
		}
		hash[curSum]++ // 记录一个前缀和
	}
	return count
}