560. 和为K的子数组

题目描述：

给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的子数组的个数 。

子数组是数组中元素的连续非空序列。

示例 1：

输入：nums = [1,1,1], k = 2
输出：2

示例 2：

输入：nums = [1,2,3], k = 3
输出：2

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

---

解题分析及思路：

方法一：前缀和

思路：

这段代码采用前缀和的方法来解决和为k的连续子数组个数的问题。通过计算前缀和，将问题转化为求解两个前缀和之差等于k的情况。

具体来说，假设数组的前缀和数组为prefixSum，其中prefixSum[i]表示从数组起始位置到第i个位置的元素之和。

在遍历数组的过程中，通过维护一个哈希表 sums，其中键是前缀和，值是该前缀和出现的次数。

在每次迭代中，累加当前元素到前缀和sum，然后检查是否存在前缀和为sum-k的情况。如果存在，说明从某个位置到当前位置的连续子数组的和为k，将对应的次数累加到结果中。

最终，通过遍历一次数组，可以统计出和为k的连续子数组的个数，时间复杂度为O(n)，其中n为数组的长度。

func subarraySum(nums []int, k int) (result int) {
	sums := make(map[int]int)
	sums[0] = 1
	sum := 0
	for _, num := range nums {
		sum += num
		if v, ok := sums[sum-k]; ok {
			result += v
		}
		sums[sum]++
	}
	return
}

复杂度：

• 时间复杂度：O(N)，其中 N 是 nums 的长度
• 空间复杂度：O(N)

执行结果：

• 执行耗时:34 ms,击败了88.40% 的Go用户
• 内存消耗:7.87 MB,8.36% 的Go用户