560. 和為 K 的子數組 - 前綴和思想

在算法題中，前綴和是一種能快速計算 “數組中某段連續元素之和” 的預處理方法，核心思路是 “提前計算并存儲中間結果，避免重復計算”

前綴和的定義：

對于一個數組 nums，我們可以創建一個 “前綴和數組” prefix，其中 prefix[i] 表示 “數組 nums 中前 i 個元素的和”（注意：這里的 “前 i 個” 通常從第 1 個元素開始算）。
以上面的步數數組為例：

• prefix[0] = 0（約定的初始值，方便計算）
• prefix[1] = 第1天步數 = 3
• prefix[2] = 第1天 + 第2天 = 3 + 1 = 4
• prefix[3] = 第1天 + 第2天 + 第3天 = 3 + 1 + 4 = 8
• prefix[4] = 前4天總和 = 3 + 1 + 4 + 2 = 10
• prefix[5] = 前5天總和 = 3 + 1 + 4 + 2 + 5 = 15

所以前綴和數組是 [0, 3, 4, 8, 10, 15]。
前綴和的妙用：快速算 “區間和”有了前綴和數組，計算 “從第 l 天到第 r 天的總步數” 時，直接用：
區間和 = prefix [r] - prefix [l-1]

比如：

• 第 2 天到第 4 天：l=2，r=4 → prefix[4] - prefix[1] = 10 - 3 = 7（和之前手動算的一致）
• 第 1 天到第 3 天：l=1，r=3 → prefix[3] - prefix[0] = 8 - 0 = 8（正確）

題目描述

https://leetcode.cn/problems/subarray-sum-equals-k/description/?envType=study-plan-v2&envId=top-100-liked

給你一個整數數組 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

題解

class Solution {public int subarraySum(int[] nums, int k) {int len  = nums.length;int preSum = 0; // 存儲前綴和HashMap<Integer,Integer> map = new HashMap(); // 用來存儲前綴和出現的次數map.put(0,1); // 初始化// 若某一個前綴和preSum恰好等于k，此時preSum - k = 0，能直接匹配到初始值 1。int res = 0;for(int x: nums){preSum += x; // 計算前綴和/*假設當前前綴和是preSum（對應數組前 i 個元素的和）我們要找 “和為 k 的子數組”，也就是找兩個前綴和 preSum[i] 和 preSum[j]（j < i），使得：preSum[i] - preSum[j] = k變形后就是：preSum[j] = preSum[i] - k需要找到之前preSum[j]出現過幾次，那么就有幾個子數組和為k*/res += map.getOrDefault(preSum - k, 0);// 更新前綴和出現的次數map.put(preSum, map.getOrDefault(preSum, 0) + 1);}return res;}
}

核心問題：如何用前綴和表示 “子數組的和”？

任意一個子數組的和，都可以表示為 “兩個前綴和的差”。
比如：

• 子數組 [1]（索引 1）的和 = 1對應：preSum[2] - preSum[1] = 3 - 2 = 1
• 子數組 [3]（索引 2）的和 = 3對應：preSum[3] - preSum[2] = 6 - 3 = 3
• 子數組 [2,1]（索引 0-1）的和 = 3對應：preSum[2] - preSum[0] = 3 - 0 = 3

關鍵邏輯：“子數組和為 k” 等價于什么？

我們要找 “和為 k 的子數組”，也就是找兩個前綴和 preSum[i] 和 preSum[j]（j < i），使得：
preSum[i] - preSum[j] = k
變形后就是：
preSum[j] = preSum[i] - k
這句話的意思是：如果當前的前綴和是 preSum[i]，那么只要之前出現過等于 preSum[i] - k 的前綴和（記為 preSum[j]），那么子數組 nums[j…i-1] 的和就一定是 k。