題目描述
給定一個整數數組 nums 和一個整數 k，請統計并返回該數組中和為 k 的子數組的數量。
子數組是數組中連續的非空元素序列。

示例

輸入：nums = [1,2,3], k = 3  
輸出：2  
解釋：子數組 [1,2] 和 [3] 滿足和為 3。

---

方法思路：前綴和 + 哈希表

核心思想

暴力枚舉所有子數組的時間復雜度為 O(n2)，無法處理大規模數據。利用前綴和與哈希表的結合，可以在 O(n) 時間內高效解決問題。

關鍵步驟

1. 前綴和
   計算到當前元素為止的前綴和 currentSum。例如，遍歷到第 i 個元素時，前綴和為 nums[0] + nums[1] + ... + nums[i]。

2. 哈希表優化

   • 哈希表 prefixSumMap 存儲每個前綴和的出現次數。
   • 若存在某個前綴和 prefixSum，使得 currentSum - prefixSum = k，則說明從 prefixSum 對應的索引之后到當前位置的子數組和為 k。
   • 通過哈希表快速查找 currentSum - k 是否存在，并累加其出現次數。

3. 初始化技巧
   初始化哈希表為 {0: 1}，表示前綴和為 0 出現了一次，用于處理從數組起始位置到當前位置的子數組和為 k 的情況。

---

代碼實現

import java.util.HashMap;
import java.util.Map;class Solution {public int subarraySum(int[] nums, int k) {Map<Integer, Integer> prefixSumMap = new HashMap<>();prefixSumMap.put(0, 1); // 初始化：前綴和為0時出現1次int currentSum = 0;     // 當前前綴和int result = 0;         // 統計結果for (int num : nums) {currentSum += num;  // 更新當前前綴和// 若存在前綴和為 (currentSum - k)，則累加其出現次數if (prefixSumMap.containsKey(currentSum - k)) {result += prefixSumMap.get(currentSum - k);}// 將當前前綴和加入哈希表，并更新出現次數prefixSumMap.put(currentSum, prefixSumMap.getOrDefault(currentSum, 0) + 1);}return result;}
}

---

復雜度分析

• 時間復雜度：O(n)，遍歷數組一次。
• 空間復雜度：O(n)，哈希表存儲最多 n 個不同的前綴和。

---

示例解析

以 nums = [1, 2, 3]，k = 3 為例：

遍歷元素	currentSum	currentSum - k	結果累加	哈希表更新
1	1	1 - 3 = -2	0	{0:1, 1:1}
2	3	3 - 3 = 0	0 + 1 =1	{0:1, 1:1, 3:1}
3	6	6 - 3 = 3	1 + 1 =2	{0:1, 1:1, 3:1, 6:1}

• 結果：最終 result = 2，對應子數組 [1,2] 和 [3]。

---

總結

1. 前綴和與哈希表的結合是解決子數組和問題的經典方法，適用于大規模數據。
2. 初始化哈希表為 {0:1} 是關鍵，確保能正確統計到從數組起始位置開始的子數組。
3. 通過空間換時間，將時間復雜度從 O(n2) 優化到 O(n)。