兩種解法詳解：暴力枚舉與前綴和+哈希表尋找和為k的子數組

在解決數組中和為k的連續子數組個數的問題時，我們可以采用不同的方法。本文將詳細解析兩種常見的解法：暴力枚舉法和前綴和結合哈希表的方法，分析它們的思路、優缺點及適用場景。

---

問題描述

給定一個整數數組 nums 和一個整數 k，要求找到所有和為 k 的連續子數組的個數。

示例：

輸入：nums = [1,1,1], k = 2
輸出：2
解釋：[1,1]（前兩個元素）和 [1,1]（后兩個元素）各為一種情況。

---

解法一：暴力枚舉法

思路分析

暴力枚舉法的核心思想是遍歷所有可能的子數組，計算它們的和是否等于 k。具體來說：

• 外層循環固定子數組的起始位置 start。
• 內層循環從 start 出發，逐步擴展子數組的結束位置 j，并累加元素和。
• 當子數組和等于 k 時，計數器增加。

代碼實現

public static int subarraySum_1(int[] nums, int k) {int count = 0;for (int start = 0; start < nums.length; start++) {int sum = 0;for (int j = start; j < nums.length; j++) {sum += nums[j];if (sum == k) {count++;}}}return count;
}

復雜度分析

• 時間復雜度：O(n2)。雙重循環遍歷所有子數組，對于長度為 n 的數組，共有 n(n+1)/2 個子數組。
• 空間復雜度：O(1)。僅使用常數空間存儲臨時變量。

適用場景

適用于小規模數據（例如 n ≤ 1e3）。當 n 較大時（如 n = 2e4），暴力法會因時間復雜度過高而超時。

---

解法二：前綴和 + 哈希表

思路分析

該方法利用前綴和的性質和哈希表的快速查詢特性，將時間復雜度優化至線性：

1. 前綴和定義：sum[i] 表示數組前 i 個元素的和。
2. 關鍵觀察：若存在 sum[j] - sum[i] = k，則子數組 nums[i+1..j] 的和為 k。
3. 哈希表優化：維護哈希表記錄前綴和出現的次數。遍歷時，若當前前綴和 sum 與 sum - k 存在，則累加次數。

代碼實現

    public static int subarraySum_2(int[] nums, int k) {int count=0;    //記錄結果int sum = 0;    //記錄前綴和//HashMap，k：存儲前綴和，V：存儲前綴和出現的次數HashMap<Integer, Integer> map = new HashMap<>();//第一個數的前綴和為0map.put(0,1);for(int i=0;i<nums.length;i++){sum +=nums[i];//注意這一定是先去判斷再添加，每個數都要去判斷一下，第一個數的前綴和已經添加了，所以需要判斷if(map.containsKey(sum-k)){count += map.get(sum-k);}//如何這個sum沒出現過：v = 0+1，出現過：v = 原來v + 1;map.put(sum,map.getOrDefault(sum,0)+1);}return count;}

復雜度分析

• 時間復雜度：O(n)。只需一次遍歷數組，哈希表查詢和插入操作均為 O(1)。
• 空間復雜度：O(n)。哈希表最多存儲 n 個不同的前綴和。

關鍵點

• 哈希表初始化：預先放入 (0, 1)，處理以第一個元素開頭的子數組和為 k 的情況。
• 負數處理：數組中可能存在負數，導致前綴和重復出現，哈希表需正確統計次數。

---

方法對比

方法	時間復雜度	空間復雜度	適用場景
暴力枚舉法	O(n2)	O(1)	小規模數據
前綴和 + 哈希表法	O(n)	O(n)	大規模數據

---

總結

• 暴力枚舉法思路簡單，但僅適用于小規模數據。
• 前綴和+哈希表通過空間換時間，將復雜度降至線性，是處理大規模數據的高效方法。
• 特別注意哈希表的初始化與更新邏輯，確保正確處理所有邊界情況。

相關題目：LeetCode 560. 和為K的子數組