【優先算法】思還故里閭，欲歸道無因

本篇博客給大家帶來的是前綴和算法的知識點, 也是一樣通過OJ題理解,掌握,應用該算法.
🐎文章專欄: 算法
🚀若有問題評論區見
? 歡迎大家點贊評論收藏分享
如果你不知道分享給誰,那就分享給薯條.
你們的支持是我不斷創作的動力 .

王子,公主請閱🚀

要開心
- 要快樂
- - 順便進步
- 1. 和為K的子數組
- 2. 和可被 K 整除的?數組(藍橋杯真題)
- 3. 連續數組
- 4. 矩陣區域和

要開心

要快樂

順便進步

1. 和為K的子數組

題目鏈接: 560. 和為 K 的子數組

題目描述:

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

子數組是數組中元素的連續非空序列。

示例 1：

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

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

解法一: 暴力解法

定義計數變量count, 兩層循環遍歷數組, 每次 j 從 i 的位置開始,
找到滿足 [ i , j ] 區間元素和等于k時,count++. 時間復雜度為O(N^2)

解法二: 前綴和 + 哈希表

1. 問題轉換并分析

①是以 i 位置為結尾的子數組,且①滿足數組元素為 k.
由此圖便可將問題轉化為: 當遍歷數組到 i 位置時, [ 0 , i-1 ]區間中前綴和為sum[i] - k的個數.

這個時候不要直接去求前綴和數組, 然后遍歷找滿足條件的前綴和. 如果這么做那時間復雜度還是O(N^2)并且空間復雜度還是O(N), 并不見得比暴力解法要好.
要找前綴和并且其滿足sum[i] - k, 可以利用哈希表來找, 哈希表本身就是用來查找的. 哈希表: <前綴和,出現次數>

2. 算法思路

設 i 為數組中的任意位置，用 sum[i] 表示 [0, i] 區間內所有元素的和。
想知道有多少個「以 i 為結尾的和為 k 的子數組」，就要找到有多少個起始位置為 x1, x2,
x3… 使得 [x, i] 區間內的所有元素的和為 k 。那么 [0, x] 區間內的和是不是就是
sum[i] - k 了。于是問題就變成：
? 找到在 [0, i - 1] 區間內，有多少前綴和等于 sum[i] - k 的即可。

3. 處理細節

1. 我們不用真的初始化一個前綴和數組，因為我們只關心在 i 位置之前，有多少個前綴和等于sum[i] - k 。因此，我們僅需用一個哈希表，一邊求當前位置的前綴和，一邊存下之前每?種前綴和出現的次數。不要把前綴和都求出來后再加入哈希表, 原本應該是[ 0 , i-1 ] 的前綴和,但求完一并加入會使 [ i , n-1] 的前綴和也加進來, 假設[ i , n-1 ] 也有滿足條件的前綴和, 就會多算.

2. 如果整個數組和為 k , 那么此時并不存在一個區間讓我去找前綴和 = sum[i] - k, 但是sum[i] = k 這個情況確實存在, 所以在我開始遍歷數組之前, 應該先map.put(0,1), sum[i] - k = 0時, 次數賦為1.

4. 代碼實現

class Solution {public int subarraySum(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<>();//將前綴和為0的初始次數設置為1, 因為 k 有可能等于nums數組中某個元素的值.map.put(0,1);int sum = 0,ret = 0;for(int x : nums) {sum += x;//計算當前位置的前綴和.ret += map.getOrDefault(sum-k,0);//統計結果.map.put(sum,map.getOrDefault(sum,0)+1);//將當前位置的前綴和sum加入哈希表.}return ret;}
}

2. 和可被 K 整除的?數組(藍橋杯真題)

題目鏈接: 974. 和可被 K 整除的?數組

題目描述:

給定一個整數數組 nums 和一個整數 k ，返回其中元素之和可被 k 整除的非空子數組的數目。

子數組是數組中連續的部分。

示例 1：

輸入：nums = [4,5,0,-2,-3,1], k = 5
輸出：7
解釋：
有 7 個子數組滿足其元素之和可被 k = 5 整除：
[4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2:

輸入: nums = [5], k = 9
輸出: 0

解法一: 暴力枚舉

做法與上題基本一致, 就是枚舉出所有子數組的和, 時間復雜度為O(N^2).

解法二: 前綴和 + 哈希表

第一點必要前置知識:

1. 同余定理
如果(a - b) % p = 0 , 那么 a % p = b % p . 即如果兩個數相減的差能被 p 整除，那么這兩個數對 p 取模的結果相同. 例如: (7 - 4) % 3 = 0, 7 % 3 = 1, 4 % 3 = 1;

根據同余定理就可以把問題轉換成, 在[0 , i-1]區間中找到滿足前綴和 % k 等于 sum[i] % k 的所有前綴和. (這也是本題的核心.)

2. 負數取模

C++和Java中, 負數 % 正數結果為負數, 為了防止重復算,統一將結果化為正數. 比如 -1 % 3 = -1 換成 (-1 % 3 + 3) % 3 = 2 . 即 a % p -> (a % p + p) % p .

第二: 具體步驟(與上題無異, 不同的是,此題中map第一個位置放的時前綴和 % k 的值. 并且確保是正數.)

設 i 為數組中的任意位置，? sum[i] 表示 [0, i] 區間內所有元素的和。
? 想知道有多少個「以 i 為結尾的可被 k 整除的子數組」，就要找到有多少個起始位置為 x1, x2, x3… 使得 [x, i] 區間內的所有元素的和可被 k 整除。
? 設 [0, x ] (x < i)區間內所有元素之和等于 a ， [0, i] 區間內所有元素的和等于 b ，可得
(b - a) % k == 0 。
? 由同余定理可得， [0, x ] 區間與 [0, i] 區間內的前綴和同余。于是問題就變成：
? 找到在 [0, i - 1] 區間內，有多少前綴和的余數等于 sum[i] % k 的即可。
我們不用真的初始化?個前綴和數組，因為我們只關心在 i 位置之前，有多少個前綴和等于sum[i] - k 。因此，我們僅需用一個哈希表，一邊求當前位置的前綴和，一邊存下之前每?種前綴和出現的次數。

第三代碼實現

class Solution {public int subarraysDivByK(int[] nums, int k) {Map<Integer,Integer> map = new HashMap<Integer,Integer>();map.put(0,1);//還是一樣的,[0,i] 當sum = k時,不存在區間,但sum[i] = k存在.int sum = 0,ret = 0;for(int x : nums) {sum += x;//當前位置的前綴和int tmp = (sum % k + k) % k;//前綴和模k 的余數,原本是sum % k, 但是Java和C++存在負數模正數等于負數的問題,一并化成正數.ret += map.getOrDefault(tmp,0);map.put(tmp,map.getOrDefault(tmp,0)+1);}return ret;}
}

3. 連續數組

題目鏈接: 525. 連續數組

題目描述:

給定一個二進制數組 nums , 找到含有相同數量的 0 和 1 的最長連續子數組，并返回該子數組的長度。

示例 1:

輸入: nums = [0,1]
輸出: 2
說明: [0, 1] 是具有相同數量 0 和 1 的最長連續子數組。
示例 2:

輸入: nums = [0,1,0]
輸出: 2
說明: [0, 1] (或 [1, 0]) 是具有相同數量0和1的最長連續子數組。

1. 暴力枚舉

枚舉出所有子數組, 檢查子數組是否滿足要求,時間復雜度為O(N^2).

2. 前綴和 + 哈希表

第一問題分析與轉換
原數組中的元素只有0和1, 題目要求的是 0 和 1 個數相等的最長子數組, 將所有的 0 換成 -1, 問題就轉換成求和為0的最長子數組的長度.

第二處理細節

1. 哈希表<In,In>的兩個位置分別存放 [ 0 , i ]前綴和與位置 i .

2. 當區間[ 0 , i ]的sum[i] = 0時, 0 < j < i,不存在[0 , j] 區間. 默認一個前綴和為0的情況, 只能以 -1 為結束位置.

3. 如果有重復的sum[ i ] , 保留前面先算出來的 <sum ,i>, 舍棄后面的, 因為先算出來的更靠左邊, 離 i 的距離更大, 本題要求的就是最大長度.

第三步驟

設 i 為數組中的任意位置，? sum[i] 表? [0, i] 區間內所有元素的和。
想知道最?的「以 i 為結尾的和為 0 的?數組」，就要找到從左往右第?個 x1 使得
[x1, i]區間內的所有元素的和為 0 。那么 [0, x1 - 1] 區間內的和是不是就是 sum[i] 了。于是問題
就變成：
? 找到在 [0, i - 1] 區間內，第?次出現 sum[i] 的位置即可。
我們不?真的初始化?個前綴和數組，因為我們只關?在 i 位置之前，第?個前綴和等于 sum[i]的位置。因此，我們僅需??個哈希表，?邊求當前位置的前綴和，?邊記錄第?次出現該前綴和的
位置。

第四代碼實現

class Solution {public int findMaxLength(int[] nums) {Map<Integer,Integer> hash = new HashMap<>();hash.put(0,-1); //當[0,i]sum = 0時,默認存在一個前綴和為0的情況.并且以-1為結束位置.int sum = 0,ret = 0;for(int i = 0;i < nums.length;++i) {if(nums[i] == 0) {sum += -1; //將數組中所有的 0 替換成 -1.}else {sum += nums[i];//求出當前位置的前綴和}if(hash.containsKey(sum-0)) {ret = Math.max(ret,i - hash.get(sum));}else{//有重復的只保留前面的那一對<sum,i>.  hash.put(sum,i);}}return ret;}
}