目錄
五：和為 k 的子數組（medium）
題目鏈接：560. 和為 K 的子數組 - 力扣（LeetCode）
解法：
代碼：
六：和可被 K 整除的子數組（medium）
題目鏈接：974. 和可被 K 整除的子數組 - 力扣（LeetCode）
解法：
代碼：
七：連續數組（medium）
題目鏈接：525. 連續數組 - 力扣（LeetCode）
解法：
代碼：
八：矩陣區域和（medium）
題目鏈接：1314. 矩陣區域和 - 力扣（LeetCode）
解法：
代碼：
五：和為 k 的子數組（medium）
題目鏈接：560. 和為 K 的子數組 - 力扣（LeetCode）
解法：
解法二（前綴和）：
設 i 為數組中的任意位置，用 sum[i] 表示? [0, i] 區間內所有元素的和。
想知道有多少個「以 i 為結尾的和為 k 的子數組」，就要找到有多少個起始位置為 x1, x2, x3... 使得 [x, i] 區間內的所有元素的和為 k 。那么 [0, x] 區間內的和是不是就是 sum[i] - k 了。
于是問題就變成：
- 找到在 [0, i - 1] 區間內，有多少前綴和等于 sum[i] - k 的即可。
我們不用真的初始化?個前綴和數組，因為我們只關心在 i 位置之前，有多少個前綴和等于
sum[i] - k 。因此，我們僅需??個哈希表，?邊求當前位置的前綴和，?邊存下之前每?種
前綴和出現的次數。
代碼：
C++：
java：
六：和可被 K 整除的子數組（medium）
題目鏈接：974. 和可被 K 整除的子數組 - 力扣（LeetCode）
（本題是某一年的藍橋杯競賽原題）
解法：
前置知識：
- 同余定理
如果 (a - b) % n == 0 ，那么我們可以得到?個結論： a % n == b % n 。?文字敘述就是，如果兩個數相減的差能被 n 整除，那么這兩個數對 n 取模的結果相同。
例如： (26 - 2) % 12 == 0 ，那么 26 % 12 == 2 % 12 == 2 。
- c++ 中負數取模的結果，以及如何修正「負數取模」的結果
a. c++ 中關于負數的取模運算，結果是「把負數當成正數，取模之后的結果加上?個負號」。
例如： -1 % 3 = -(1 % 3) = -1
b. 因為有負數，為了防?發?「出現負數」的結果，以 (a % n + n) % n 的形式輸出保證為正。
例如： -1 % 3 = (-1 % 3 + 3) % 3 = 2
算法思路：
思路與上 道題的思路相似。
設 i 為數組中的任意位置，用? sum[i] 表示? [0, i] 區間內所有元素的和。
想知道有多少個「以 i 為結尾的可被 k 整除的子數組」，就要找到有多少個起始位置為 x1, x2, x3... 使得? [x, i] 區間內的所有元素的和可被 k 整除。
設 [0, x - 1] 區間內所有元素之和等于 a ， [0, i] 區間內所有元素的和等于 b ，可得
(b - a) % k == 0 。
由同余定理可得， [0, x - 1] 區間與 [0, i] 區間內的前綴和同余。于是問題就變成：
- 找到在 [0, i - 1] 區間內，有多少前綴和的余數等于 sum[i] % k 的即可。
我們不用真的初始化?個前綴和數組，因為我們只關心在 i 位置之前，有多少個前綴和等于
sum[i] - k 。因此，我們僅需用?個哈希表，?邊求當前位置的前綴和，?邊存下之前每?種前
綴和出現的次數。
代碼：
C++：
java：
七：連續數組（medium）
題目鏈接：525. 連續數組 - 力扣（LeetCode）
解法：
稍微轉化?下題目，就會變成我們熟悉的題：
本題讓我們找出?段連續的區間， 0 和 1 出現的次數相同。
如果將 0 記為 -1 ， 1 記為 1 ，問題就變成了找出?段區間，這段區間的和等于 0 。
于是，就和 560. 和為 K 的子數組 這道題的思路?樣 
設 i 為數組中的任意位置，? sum[i] 表示 ? [0, i] 區間內所有元素的和。
想知道最?的「以 i 為結尾的和為 0 的子 0數1組」，就要找到從左往右第?個 x1 使得 [x1, i]
區間內的所有元素的和為 0 。那么 [0, x1 - 1] 區間內的和是不是就是 sum[i] 了。于是問題
就變成：
找到在 [0, i - 1] 區間內，第?次出現 sum[i] 的位置即可。
我們不?真的初始化?個前綴和數組，因為我們只關?在 i 位置之前，第?個前綴和等于 sum[i]
的位置。因此，我們僅需??個哈希表，?邊求當前位置的前綴和，?邊記錄第?次出現該前綴和的
位置。
代碼：
C++：
java：
八：矩陣區域和（medium）
題目鏈接：1314. 矩陣區域和 - 力扣（LeetCode）
解法：
?維前綴和的簡單應用題，關鍵就是我們在填寫結果矩陣的時候，要找到原矩陣對應區域的「左上
角」以及「右下角」的坐標（推薦畫圖）
回顧：
左上?坐標： x1 = i - k ， y1 = j - k ，但是由于會「超過矩陣」的范圍，因此需要對 0 取?個 max 。因此修正后的坐標為： x1 = max(0, i - k), y1 = max(0, j - k) ;
右下?坐標： x1 = i + k ， y1 = j + k ，但是由于會「超過矩陣」的范圍，因此需要對 m - 1 ，以及 n - 1 取?個 min 。因此修正后的坐標為： x2 = min(m - 1, i + k) ,?? y2 = min(n - 1, j + k) 。
然后將求出來的坐標代入到「二維前綴和矩陣」的計算公式上即可~（但是要注意下標的映射關
系） 
代碼：
C++：
java：
)
設計模式)
)
)