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）。

實現

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 時，也能被正確統計，計數+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
//}

---