題目描述

給定一個整數數組?nums?和一個整數?k，請統計并返回該數組中和為?k?的連續子數組的個數。

示例 1：

輸入：nums = [1,1,1], k = 2
輸出：2

示例 2：

輸入：nums = [1,2,3], k = 3
輸出：2

提示：

• 1 <= nums.length <= 2 * 10^4
• -1000 <= nums[i] <= 1000
• -10^7 <= k <= 10^7

解題思路

這道題要求找出和為k的連續子數組的個數。我們可以有多種思路：

1. 暴力解法

最直觀的方法是枚舉所有可能的子數組，計算它們的和，并統計和為k的子數組個數。但這種方法的時間復雜度是O(n2)，對于較大規模的數組會超時。

2. 前綴和 + 哈希表

更高效的解法是使用前綴和和哈希表的組合：

• 使用一個變量?sum?記錄從數組起始位置到當前位置的所有元素之和
• 使用哈希表?prefixSum?記錄每種前綴和出現的次數
• 對于每個位置，我們檢查?sum - k?是否在哈希表中存在
  • 如果存在，說明從某個位置到當前位置的子數組和為k
  • 將哈希表中?sum - k?對應的次數加到結果中

這種方法的時間復雜度為O(n)，空間復雜度為O(n)。

代碼實現

class Solution {public int subarraySum(int[] nums, int k) {int count = 0;int sum = 0;// 哈希表：前綴和 -> 出現次數HashMap<Integer, Integer> prefixSum = new HashMap<>();// 初始化：前綴和為0的情況出現了1次prefixSum.put(0, 1);for (int num : nums) {// 累加前綴和sum += num;// 如果 (sum - k) 存在于哈希表中，說明存在若干個前綴和為 (sum - k) 的子數組// 這些子數組與當前位置之間的子數組的和為kif (prefixSum.containsKey(sum - k)) {count += prefixSum.get(sum - k);}// 將當前前綴和加入哈希表，或更新其出現次數prefixSum.put(sum, prefixSum.getOrDefault(sum, 0) + 1);}return count;}
}

復雜度分析

• 時間復雜度：O(n)，其中 n 是數組的長度。我們只需要遍歷一次數組。
• 空間復雜度：O(n)，最壞情況下哈希表需要存儲 n 個不同的前綴和。

解題思路詳解

這道題的關鍵在于理解前綴和與哈希表的結合使用。前綴和是指從數組起始位置到當前位置的元素和。

如果我們有兩個位置 i 和 j，且它們的前綴和之差等于 k，即?prefixSum[j] - prefixSum[i] = k，那么從位置 i+1 到位置 j 的子數組和就是 k。

轉化一下等式：prefixSum[j] - k = prefixSum[i]，所以我們只需要知道在位置 j 之前有多少個位置 i 滿足?prefixSum[i] = prefixSum[j] - k。

使用哈希表記錄每個前綴和出現的次數，當我們遍歷到位置 j 時，就可以直接查詢有多少個位置 i 滿足條件，從而在O(1)時間內知道有多少個和為k的子數組以位置 j 結尾。