Problem: 560. 和為 K 的子數組
題目：給你一個整數數組 nums 和一個整數 k ，請你統計并返回 該數組中和為 k 的子數組的個數 。子數組是數組中元素的連續非空序列。
【LeetCode 熱題 100】560. 和為 K 的子數組——（解法二）前綴和+哈希表
整體思路
這段代碼的目的是計算一個整數數組 nums 中，和為特定值 k 的 連續子數組 的個數。例如，對于 nums = [1, 1, 1] 和 k = 2，連續子數組 [1, 1] 有兩個，它們分別從索引 0 和 1 開始，所以結果是 2。
該算法采用了一種基于 前綴和（Prefix Sum） 的暴力枚舉法。其核心邏輯步驟如下：
-
預處理：計算前綴和
- 算法首先創建了一個比原數組
nums長一個單位的數組sum。sum[i]被設計用來存儲nums數組中從索引 0 到i-1的所有元素的累加和。 sum[0]初始化為 0，作為計算的基準。- 通過一次遍歷，計算出所有前綴和，即
sum[i+1] = sum[i] + nums[i]。 - 核心優勢：一旦擁有了前綴和數組，我們就可以在 O(1) 的時間內計算出任意連續子數組
nums[i...j]的和。其計算公式為sum[j+1] - sum[i]。這避免了在每次檢查子數組時都進行重復的求和計算，將一個潛在的 O(N^3) 算法優化到了 O(N^2)。
- 算法首先創建了一個比原數組
-
枚舉所有子數組并校驗
- 接下來，代碼使用兩層嵌套的循環來枚舉出所有的連續子數組。
- 外層循環的變量
j代表子數組的 結束索引。 - 內層循環的變量
i代表子數組的 起始索引。 - 通過
for (j=0..n-1)和for (i=0..j)的組合，可以不重不漏地生成所有可能的(i, j)對，即所有連續子數組。 - 對于每一個由
(i, j)定義的子數組，利用前綴和數組，通過sum[j+1] - sum[i]快速得到其和。 - 將計算出的和與目標值
k進行比較。如果相等，則將計數器ans加一。
-
返回結果
- 在遍歷完所有可能的子數組后，
ans中就存儲了最終的總數，將其返回。
- 在遍歷完所有可能的子數組后，
總而言之，該算法通過預計算前綴和，然后系統地遍歷所有可能的子數組端點，來解決這個問題。雖然它不是最優解法（最優解法使用哈希表，時間復雜度為O(N)），但它是一個思路清晰且正確的暴力解法。
完整代碼
class Solution {/*** 計算和為 k 的連續子數組的個數。* @param nums 整數數組* @param k 目標和* @return 和為 k 的連續子數組的數量*/public int subarraySum(int[] nums, int k) {// 獲取數組的長度int n = nums.length;// 創建前綴和數組 sum，長度為 n+1。// sum[i] 將存儲 nums[0] 到 nums[i-1] 的和。// sum[0] = 0，作為計算的起點，代表空數組的和。int[] sum = new int[n + 1];// ans 用于累計和為 k 的子數組的數量int ans = 0;// 步驟 1: 預計算前綴和// 遍歷 nums 數組，填充 sum 數組for (int i = 0; i < n; i++) {// sum[i+1] 等于前 i 個元素的和（sum[i]）加上當前元素 nums[i]sum[i + 1] = sum[i] + nums[i];}// 步驟 2: 枚舉所有子數組// 外層循環確定子數組的結束索引 jfor (int j = 0; j < n; j++) {// 內層循環確定子數組的起始索引 i// i 的范圍是從 0 到 j，確保 i <= jfor (int i = 0; i <= j; i++) {// 利用前綴和快速計算子數組 nums[i...j] 的和// sum[j+1] 是 nums[0...j] 的和// sum[i] 是 nums[0...i-1] 的和// 兩者相減即為 nums[i...j] 的和if (sum[j + 1] - sum[i] == k) {// 如果子數組的和等于 k，計數器加 1ans++;}}}// 返回最終的計數結果return ans;}
}
時空復雜度
時間復雜度：O(N^2)
- 前綴和計算：第一個
for循環遍歷nums數組一次，用于計算前綴和。這個循環執行了N次。因此，這部分的時間復雜度是 O(N)。 - 子數組枚舉：
- 第二個（外層）
for循環的變量j從0到N-1，執行N次。 - 第三個（內層）
for循環的變量i從0到j。其執行次數依賴于j。 - 總的執行次數是
1 + 2 + 3 + ... + N，這是一個等差數列求和，結果為N * (N + 1) / 2。 - 因此，嵌套循環部分的復雜度為 O(N^2)。
- 第二個（外層）
- 循環內部操作：在最內層循環中，
sum[j + 1] - sum[i]和比較操作都是 O(1) 的。
綜合分析：
算法的總時間復雜度由各部分相加決定：O(N) + O(N^2)。在 Big O 表示法中，我們只保留最高階項，所以最終的時間復雜度是 O(N^2)。
空間復雜度：O(N)
- 主要存儲開銷：算法創建了一個名為
sum的整型數組來存儲前綴和。 - 空間大小：該數組的長度是
n + 1，其中n是輸入數組nums的長度。因此，它占用的空間與輸入規模N成線性關系。 - 其他變量：
n,ans,i,j等變量都只占用常數級別的空間，即 O(1)。
綜合分析：
算法所需的額外空間主要由前綴和數組 sum 決定。因此，空間復雜度為 O(N)。
