【每日一题】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 // 子数组个数// 外层循环：确定子数组起点 ifor i := 0; i < len(nums); i++ {sum := 0 // 初始化子数组和// 内层循环：确定子数组终点 jfor j := i; j < len(nums); j++ {sum += nums[j] // 累加子数组元素if sum == k { // 如果子数组和等于 kcnt++ // 计数器 +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）。
实现
-
遍历数组，累加前缀和 pre[j]
pre[j]=nums[0]+nums[1]+⋯+nums[j] -
用哈希表记录每个前缀和出现的次数
key = 前缀和
value = 出现次数 -
对于当前前缀和 pre，查找 pre - k 是否在哈希表里
-
如果存在，说明从之前某个位置到当前位置的子数组和为 k
-
将出现次数累加到结果
代码实现（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 时，也能被正确统计，计数+1for i := 0; i < len(nums); i++ {pre += nums[i] // 更新当前前缀和// 查找 pre - k 是否出现过，如果出现，说明从之前的位置到当前位置之间的子数组和为 kif 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, 0m := map[int]int{}m[0] = 1for 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
//}