【每日一题】Day 7

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 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107

1. 暴力法

遍历数组的每个起点 i
从 i 开始，依次往后延伸，形成子数组 nums[i:j]
计算这个子数组的和
如果等于 k，计数器 +1

代码实现（Go）：

//package main
//
//import "fmt"

func subarraySum(nums []int, k int) int {
	cnt := 0 // 子数组个数

	// 外层循环：确定子数组起点 i
	for i := 0; i < len(nums); i++ {
		sum := 0 // 初始化子数组和
		// 内层循环：确定子数组终点 j
		for j := i; j < len(nums); j++ {
			sum += nums[j] // 累加子数组元素
			if sum == k {  // 如果子数组和等于 k
				cnt++ // 计数器 +1
			}
		}
	}
	return cnt
}

//func main() {
//	nums1 := []int{1, 1, 1}
//	k1 := 2
//	fmt.Println(subarraySum(nums1, k1)) // 输出 2
//}

2. 前缀和 + 哈希表优化

前缀和的概念
使用一个叫做“前缀和”的概念。对于数组中的任何位置 j，前缀和 pre[j] 是数组中从第 1 个元素到第 j 个元素的总和。如果想知道从元素 i+1 到 j 的子数组的和，可以用 pre[j] - pre[i] 来计算。

使用 Map 来存储前缀和
在代码中，用一个 Map（哈希表）来存储每个前缀和出现的次数。这是为了快速检查某个特定的前缀和是否已经存在，以及它出现了多少次。

核心逻辑
在数组中向前移动时，逐步增加 pre（当前的累积和）。对于每个新的 pre 值，检查 pre - k 是否在 Map 中

pre - k 的意义：这个检查的意义在于，如果 pre - k 存在于 Map 中，说明之前在某个点的累积和是 pre - k。由于当前的累积和是 pre，这意味着从那个点到当前点的子数组之和恰好是 k（因为 pre - (pre - k) = k）。

实现

1. 遍历数组，累加前缀和 pre[j]
   pre[j]=nums[0]+nums[1]+⋯+nums[j]

2. 用哈希表记录每个前缀和出现的次数
   key = 前缀和
   value = 出现次数

3. 对于当前前缀和 pre，查找 pre - k 是否在哈希表里

4. 如果存在，说明从之前某个位置到当前位置的子数组和为 k

5. 将出现次数累加到结果

代码实现（Go）：

// package main

// import "fmt"

func subarraySum(nums []int, k int) int {
	cnt := 0           // 用来记录子数组的个数
	pre := 0           // 当前前缀和
	m := map[int]int{} // 或 m:=make(map[int]int)
	m[0] = 1           // 前缀和 0 出现 1 次，保证一个数字刚好等于 k 时，也能被正确统计，计数+1

	for i := 0; i < len(nums); i++ {
		pre += nums[i] // 更新当前前缀和

		// 查找 pre - k 是否出现过，如果出现，说明从之前的位置到当前位置之间的子数组和为 k
		if v, ok := m[pre-k]; ok {
			cnt += v
		}

		// 更新哈希表，记录当前前缀和出现次数
		m[pre]++
	}
	return cnt
}

// func main() {
// 	nums1 := []int{1, 1, 1}
// 	k1 := 2
// 	fmt.Println(subarraySum(nums1, k1)) // 输出 2
// }

无注释：

//package main
//
//import "fmt"

func subarraySum(nums []int, k int) int {
	cnt, pre := 0, 0
	m := map[int]int{}
	m[0] = 1

	for i := 0; i < len(nums); i++ {
		pre += nums[i]
		if v, ok := m[pre-k]; ok {
			cnt += v
		}
		m[pre]++
	}
	return cnt
}

//func main() {
//	nums1 := []int{1, 1, 1}
//	k1 := 2
//	fmt.Println(subarraySum(nums1, k1)) // 输出 2
//}