一、前綴和（Prefix Sum）算法概述

前綴和算法通過預先計算數組的累加和，可以在常數時間內回答多個區間和相關的查詢問題，是解決子數組和問題中的重要工具。

它的基本思想是通過預先計算和存儲數組的前綴和，可以在 O(1) 的時間復雜度內計算任意子數組的和。

1. 定義：
   • 對于數組 nums，其前綴和 prefix[i] 定義為從數組起始位置到第 i 個元素的累加和。

• 具體公式：prefix[i] = nums[0] + nums[1] + ... + nums[i]。

2. 計算方法：
   • 首先，創建一個額外的數組或哈希表，用來存儲每個位置的前綴和。
   • 通過一次遍歷數組，依次計算并填充這個數組或哈希表。

3. 應用：
   • 快速計算子數組和：通過前綴和，可以快速計算任意子數組的和。例如，子數組 nums[l...r] 的和可以通過 prefix[r] - prefix[l-1] 來計算，其中 l 和 r 分別是子數組的左右邊界。

• 解決相關問題：例如，最大子數組和、和為特定值的子數組個數等問題，都可以通過前綴和算法高效解決。

---

二、前綴和習題合集

1. LeetCode 930 和相同的二元子數組

• 思路：

假設原數組的前綴和數組為 sum，且子數組 (i,j] 的區間和為 goal，那么 sum[j]?sum[i]=goal。因此我們可以枚舉 j ，每次查詢滿足該等式的 i 的數量。

用哈希表記錄每一種前綴和出現的次數，假設我們當前枚舉到元素 nums[j]，我們只需要查詢哈希表中元素 sum[j]?goal 的數量即可，這些元素的數量即對應了以當前 j 值為右邊界的滿足條件的子數組的數量。

• pre[j] - pre[i]= goal —> pre[i] = pre[j] - goal

• 如果存在前綴和為 pre[j] - goal(也就是pre[i])

• 說明從某個位置 j 到當前位置 i 的子數組和為 goal

最后這些元素的總數量即為所有和為 goal 的子數組數量。

• 代碼：

class Solution {public int numSubarraysWithSum(int[] nums, int goal) {int n = nums.length; // 數組的長度Map<Integer,Integer> map = new HashMap<>(); // 使用哈希表來記錄前綴和的出現次數int pre_J = 0; // 初始前綴和為0int ans = 0; // 計數器，用來記錄符合條件的子數組個數for (int i = 0; i < n; i++) {map.put(preJ, map.getOrDefault(pre_J, 0) + 1); // 更新前綴和為 preJ 的出現次數pre_J += nums[i]; // 計算當前位置的前綴和//pre[j] - pre[i]= goal //pre[i] = pre[j] - goal// 計算滿足條件的子數組個數// 如果存在前綴和為 pre[j] - goal(也就是pre[i])//說明從某個位置 j 到當前位置 i 的子數組和為 goalans += map.getOrDefault(pre_J - goal, 0);}return ans; // 返回符合條件的子數組個數}
}

---

2. LeetCode 560 和為K的子數組

• 這里咋一看好像是可以用滑動窗口哈 ，但是發現數據里有負數。因為nums[i]可以小于0，也就是說右指針j向后移1位不能保證區間會增大，左指針i向后移1位也不能保證區間和會減小。

• 思路 ： 同上一題類似

前綴和 + 哈希

class Solution {public static int subarraySum(int[] nums, int k) {int n = nums.length; // 獲取數組長度Map<Integer,Integer> map = new HashMap<>(); // 創建哈希表，用于存儲前綴和及其出現次數int sum = 0; // 初始化前綴和為0int ans = 0; // 初始化結果為0map.put(sum,1); // 將初始的前綴和0放入哈希表，并設其出現次數為1// 遍歷數組for(int num : nums){sum += num; // 計算當前位置的前綴和// 如果哈希表中存在前綴和為sum-k的項，則說明存在和為k的子數組 sum - (sum-k) = kif(map.containsKey(sum - k)){ans += map.get(sum - k); // 更新結果，累加前綴和為sum-k的子數組數量}map.put(sum, map.getOrDefault(sum, 0) + 1); // 更新哈希表，將當前前綴和放入，并更新出現次數}return ans; // 返回結果}
}

• 初始時，將前綴和為 0 放入哈希表 map 中，表示在初始狀態下存在一個前綴和為 0 的情況，出現次數為 1。

• 如果 map 中存在 sum - k，則說明從之前的某個位置到當前位置的子數組的和為 k。這是因為 sum - (sum - k) = k。

• 如果存在這樣的前綴和，則將該前綴和的出現次數累加到 ans 中。

---

3. LeetCode 523 連續的子數組和

• 這里要用到數學知識——同余定理

1. 前綴和的定義： 設 preSum[i] 表示 nums 數組從 0 到 i 的元素之和。

   • 如果存在一個子數組 nums[j..i] （j < i），其和是 k 的倍數，則 preSum[i] - preSum[j-1] 必須是 k 的倍數。

2. 利用余數的性質(同余定理)：

   • 如果 preSum[i] 和 preSum[j-1] 對 k 取余得到相同的結果，即 (preSum[i] - preSum[j-1]) % k == 0，則存在這樣的子數組。
   • a%k = b%k ,則 （a-b）%k =0 滿足條件

4. 使用哈希表記錄余數： 使用哈希表來記錄每個余數第一次出現的位置。

---

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int n = nums.length;int[] pre = new int[n + 1];for (int i = 1; i <= n; i++) {pre[i] = pre[i - 1] + nums[i - 1]; // 計算前綴和}Set<Integer> set = new HashSet<>();for (int i = 2; i <= n; i++) {set.add(pre[i - 2] % k); // 將前綴和前兩項的同余結果加入集合if (set.contains(pre[i] % k)) return true; // 如果當前前綴和對k取模的結果在集合中已經存在，說明找到了符合條件的子數組}return false; // 如果遍歷完沒有找到符合條件的子數組，返回false}
}

---

更新于：

本篇blog會持續更新哦~