刷题使我快乐，满脸开心.jpg

• 来源：力扣（LeetCode）
• 链接：https://leetcode.cn/problems/subarray-sum-equals-k/
• 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

题目

给你一个整数数组 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

思路

暴力可破，关键就在于怎么优化了。

前缀和

• 对于这类连续数组求和的场景，前缀和是个很不错的思路。

即用一个连续累计加和的数组做辅助，以各个累计和之间的间隙差值来尝试匹配结果

哈希表

• 而对于匹配间隙来说，我们就需要一个方式来进行搜索，这里可以考虑哈希表，搜索匹配更快。
• 因为有负数和0存在，所以很有可能会出现累加和出现重复，所以哈希表需要记录数量，而不是单单记录是否存在。
• 不过哈希表也有一个弊端，那就是累加和需要的是有序，但对于是否存在这个结果上，哈希表是无序的，所以在代码编排上，我们就需要从前往后搜索匹配，保证结果的正确性。

至此，也就没有太多可说的了，细节在代码注释了。

代码

func subarraySum(nums []int, k int) int {
	// 求前缀和数组
	sums := make([]int, len(nums)+1)
	for i := range nums {
		sums[i+1] = sums[i] + nums[i]
	}

	// map缓存前缀和
	sumMap := make(map[int]int, len(nums))
	// 初始化
    sumMap[0] = 1
	res := 0
	// nums[0] 没有'前缀'，所以 sums[0] 无实际意义，需从 sums[1] 开始
	for i := 1; i < len(sums); i++ {
		if _, ok := sumMap[sums[i]-k]; ok {
			// 如果多次进入，说明有多个起点可以累加至 i 位置满足情况
			res += sumMap[sums[i]-k]
		}
		// 对累加过来的结果进行 +1，后续有相同累加结果时再 +1
		// 后续再出现 sums[i]-k == 0 时，说明有两个位置可以累加至此满足情况
		// 确实应该 +2，所以不用担心正确性
		sumMap[sums[i]] += 1
	}
	return res
}