柚子快報邀請碼778899分享：算法【Java】 —— 前綴和

http://yzkb.51969.com/

模板引入

一維前綴和

https://www.nowcoder.com/share/jump/9257752291725692504394

解法一：暴力枚舉

在每次提供 l 與 r 的時候，都從 l 開始遍歷數(shù)組，直到遇到 r 停止，這個方法的時間復雜度為 O(N * q)

解法二：前綴和

如果我們事先就知道所有從 0 開始的子數(shù)組的前綴和的話，那么要計算 從 l 到 r 之間的字數(shù)組的和的時候，我們就可以利用這個已知的前綴和數(shù)組進行計算，也就是 ans = dp[r] - dp[l] + nums[l]

時間復雜度為 O(N + q) , 空間復雜度為 O(N)

import java.util.Scanner;

// 注意類名必須為 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int q = in.nextInt();

long[] arr = new long[n];

for(int i = 0; i < n; i++) {

arr[i] = in.nextInt();

}

//構建前綴和數(shù)組

long[] dp = new long[n+1];

for(int i = 1; i <= n; i++) {

dp[i] = dp[i-1] + arr[i-1];

}

while(q > 0) {

int l = in.nextInt();

int r = in.nextInt();

System.out.println(dp[r] - dp[l] + arr[l-1]);

q--;

}

}

}

二維前綴和

https://www.nowcoder.com/share/jump/9257752291725693083065

解法一：暴力枚舉

直接遍歷矩陣，時間復雜度為 O(N2 * q)

解法二：前綴和

和上面那一道題目一樣，我們先預處理一個前綴和數(shù)組，只不過這次是一個二維數(shù)組，我們需要討論一下：

由上圖可知，要想求 dp[i][j]，我們可以利用上面的關系來推導，也就是 dp[i][j] 等于三塊顏色的區(qū)域 加上 原矩陣對應的 nums[i][j]

dp[i-1][j] 等于藍色區(qū)域加上綠色區(qū)域，dp[i][j-1] 等于藍色區(qū)域加上橙色區(qū)域，dp[i-1][j-1] 等于藍色區(qū)域

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + nums[i][j]

但是要注意可能會出現(xiàn)數(shù)組越界訪問的情況，因為當 i = 0 或者 j = 0 的時候 ，dp[i][j-1] 是會發(fā)生越界訪問的，所以要避免發(fā)生越界訪問的話，我們可以加多一個外圍區(qū)域，就是將 dp 數(shù)組 在創(chuàng)建的時候，可以將 dp[][] = new int[n+1][m+1]，也就是比原先數(shù)組多一行和多一列

這樣的話，我們在進行 dp 數(shù)組計算的時候，下標就應該從 1 開始，對應的nums 數(shù)組的下標則是減一即可。

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + nums[i-1][j-1]

如何獲取從 (x1,y1) 到 （x2,y2) 之間的區(qū)域的和

因為正好是x1 ，y1, x2, y2 可以對應我們的 dp 數(shù)組，所以直接使用

藍色區(qū)域是我們要求的區(qū)域，藍色區(qū)域 等于 = dp[x2][y2] - (dp[x1-1][y2] + dp[x2][y1-1] - dp[x1-1][y1-1]

import java.util.Scanner;

// 注意類名必須為 Main, 不要有任何 package xxx 信息

public class Main {

public static void main(String[] args) {

Scanner in = new Scanner(System.in);

int n = in.nextInt();

int m = in.nextInt();

int q = in.nextInt();

int[][] arr = new int[n][m];

for(int i = 0; i < n; i++) {

for(int j = 0; j < m; j++) {

arr[i][j] = in.nextInt();

}

}

//構建前綴和數(shù)組

long[][] dp = new long[n+1][m+1];

for(int i = 1; i <= n; i++) {

for(int j = 1; j <= m; j++) {

dp[i][j] = dp[i][j-1] + dp[i-1][j] - dp[i-1][j-1] + arr[i-1][j-1];

}

}

while(q > 0) {

int x1 = in.nextInt();

int y1 = in.nextInt();

int x2 = in.nextInt();

int y2 = in.nextInt();

System.out.println(dp[x2][y2] - (dp[x1-1][y2] + dp[x2][y1-1] - dp[x1-1][y1-1]));

q--;

}

}

}

小結

前綴和主要用于處理數(shù)組區(qū)間的和的問題。

前綴和處理二維數(shù)組（矩陣）的時候，要注意 dp 數(shù)組要擴大。

實戰(zhàn)演練

尋找數(shù)組的中心下標

https://leetcode.cn/problems/find-pivot-index/description/

解析： 中心下標表示除了這個下標對應的數(shù)字之外，其左邊區(qū)域和等于右邊區(qū)域和

區(qū)域和，我們可以聯(lián)想到前綴和來解決，由于需要比較左右兩邊的區(qū)域和，我們可以設置前綴和數(shù)組與后綴和數(shù)組。

注意事項 前綴和應該從 下標 1 開始計算，f[i] = f[i-1] + nums[i-1] 后綴和應該從下標 n - 2 開始計算，g[i] = g[i+1] + nums[i+1] 因為上面兩條公式需要利用到之前的前綴和或者后綴和，如果前綴和從0開始計算，則會數(shù)組越界訪問異常，并且題目告訴我們如果中心下標是最左端，則左側數(shù)組和為 0 ，右側也一樣，所以我們可以直接從 0 或者 n - 2 開始計算。

class Solution {

public int pivotIndex(int[] nums) {

int n = nums.length;

int[] f = new int[n];

int[] g = new int[n];

//構建前綴和數(shù)組

for(int i = 1; i < n; i++) {

f[i] = f[i-1] + nums[i-1];

}

//構建后綴和數(shù)組

for(int i = n - 2; i >= 0; i--) {

g[i] = g[i+1] + nums[i+1];

}

//查找

for(int i = 0; i < n; i++) {

if(f[i] == g[i])

return i;

}

return -1;

}

}

除自身以外數(shù)組的乘積

https://leetcode.cn/problems/product-of-array-except-self/description/

解析： 和上面的題目類似，這次是乘法，我們可以使用前綴積和后綴積來解答

這里要注意 f[0] 和 g[n-1] 要先預設置為 0，避免后續(xù)計算的時候得到的全是 0

class Solution {

public int[] productExceptSelf(int[] nums) {

int n = nums.length;

int[] f = new int[n];

int[] g = new int[n];

f[0] = 1;

g[n-1] = 1;

//構建前綴積數(shù)組

for(int i = 1; i < n; i++) {

f[i] = f[i-1] * nums[i-1];

}

//構建后綴積數(shù)組

for(int i = n - 2; i >= 0; i--) {

g[i] = g[i+1] * nums[i+1];

}

int[] ans = new int[n];

for(int i = 0; i < n; i++) {

ans[i] = f[i] * g[i];

}

return ans;

}

}

和為 K 的子數(shù)組

https://leetcode.cn/problems/subarray-sum-equals-k/description/

注意這里不能使用滑動窗口來解決?。?！

滑動窗口有一個特點就是右指針不能進行回退，所以當你要使用滑動窗口來解決子數(shù)組的時候，要保證一個前提：數(shù)組具有單調性。

而這道題目由于數(shù)組可能會出現(xiàn)負數(shù)，也就是說明數(shù)組是不具有單調性的，舉個例子：

兩塊藍色區(qū)域相加正好等于零，而中間紅色區(qū)域等于K 的時候，你使用滑動窗口，由于右指針不能回退，導致遺漏掉中間紅色數(shù)組的情況，所以，我們不能使用滑動窗口。

解法一：暴力枚舉

通過兩層 循環(huán)，獲取所有的子數(shù)組，時間復雜度為 O(N2)

解法二：前綴和加哈希表

計算 [0, i] 區(qū)間的前綴和 sum[i]

我們把要求的 K 子數(shù)組定義為以 i 結尾的子數(shù)組

如果存在 K 的子數(shù)組的話：

那么如果 i 數(shù)組前面出現(xiàn)過 子數(shù)組和為 sum[j] 的話，就說明存在 K 數(shù)組，sum[j] = sum[i] - K

我們在計算 前綴和 sum[i] 的時候，其實也就已經得知 i 數(shù)組前面所有的下標的前綴和，那么我們可以利用哈希表來保存這些數(shù)據(jù)，哈希表存儲的應該是

我們其實不需要創(chuàng)建前綴和數(shù)組 因為我們只是要利用前一個前綴和結果來推導現(xiàn)在這一個前綴和，對于前幾次的前綴和結果我們其實用不到，所以我們可以使用一個變量 sum，一直滾動累加下去即可。

要事先將 <0,1> 存進哈希表中 因為可能會出現(xiàn)一開始就得到 和為 K 的數(shù)組，此時 sum - k = 0，但是 count 卻沒有自增，所以我們事先設定存在一個前綴和 為 0 的子數(shù)組，并且出現(xiàn)次數(shù)為 1

class Solution {

public int subarraySum(int[] nums, int k) {

Map map = new HashMap<>();

map.put(0,1);

int sum = 0;

int count = 0;

for(int x : nums) {

sum += x;

if(map.containsKey(sum - k)) {

count += map.get(sum-k);

}

map.put(sum,map.getOrDefault(sum,0) + 1);

}

return count;

}

}

和可被 K 整除的子數(shù)組

https://leetcode.cn/problems/subarray-sums-divisible-by-k/description/

解析：

這里依舊不能使用滑動窗口來做 因為存在負數(shù)，不具有單調性。

補充知識：同余定理，當 (a - b) % p = 0 可以推導出 a % p = b % p，有了這個公式，我們就可以得出當存在另外幾個 b 滿足 a % p = b % p 的時候，則說明存在 和可被 K 整除的子數(shù)組，在判斷的時候，我們用到的是余數(shù)，所以在哈希表中，我們保存的應該為 <余數(shù)，余數(shù)出現(xiàn)的次數(shù)>，后面就是基本的前綴和操作了，和上面那一道題目類似。

Java 當中，負數(shù) % 正數(shù) 的結果為 負數(shù)，我們需要將結果糾正為正數(shù)，公式為 ret = (sum % k + k) % k 解釋一下，sum % k 可以得到余數(shù)，但是可能為負數(shù)，所以再加 一個 k，保證這是一個正數(shù)，但是可能會破壞余數(shù)這個特性，所以還要再次 模 k，最后的 模k 是不會影響的。

由于可能會出現(xiàn)一開始前綴和 正好為 K ，取模結果為0，此時應該預先將 <0,1> 存儲進哈希表里。

class Solution {

public int subarraysDivByK(int[] nums, int k) {

Map map = new HashMap<>();

map.put(0,1);

int sum = 0;

int count = 0;

for(int x : nums) {

sum += x;

int ret = (sum % k + k) % k;

count += map.getOrDefault(ret, 0);

map.put(ret,map.getOrDefault(ret,0) + 1);

}

return count;

}

}

連續(xù)數(shù)組

https://leetcode.cn/problems/contiguous-array/description/

解析：

由于數(shù)組只會出現(xiàn) 0 或者 1，我們要尋找最大長度的數(shù)組（滿足 0 的數(shù)量等于 1 的數(shù)量），如果要使用前綴和，我們可以將 0 設置為 -1，這樣，我們要尋找的子數(shù)組（記為 K）的和就是為 0

前綴和數(shù)組sum[i] :

此時 K = 0，那么 就是要得到目前是否存在 sum[j] 數(shù)組是等于 sun[i]，如果存在，則需要計算這個 K 數(shù)組的區(qū)間長度 = i - j

于是我們可以將前綴和 與 對應的下標索引 存到哈希表里，

我們不用真的創(chuàng)建一個前綴和數(shù)組，因為我們用不到，我們可以使用一個變量 sum 來保存當前的前綴和結果

如果當整個數(shù)組的和為 K 的時候，那么最大的長度應該為 整個數(shù)組的長度，此時 i 最大到達 nums.length - 1 ,要想獲得 數(shù)組長度，我們應該預先將 <0, -1> 存儲進哈希表中

哈希表的 put : 我們保存數(shù)據(jù)的時候，要保存的是 sum 對應的最小的索引，因為我們要求的是最大的數(shù)組長度，所以當哈希表存在 sum[i] 的時候，我們應該更新最新長度，這個時候，就不用保存進哈希表里了，因為我們不需要跟新下標索引值，如果沒有出現(xiàn)的話，那么此時 sum[i] 所對應的下標要一起保存進哈希表中。

class Solution {

public int findMaxLength(int[] nums) {

Map map = new HashMap<>();

map.put(0,-1);

int n = nums.length;

int sum = 0;

int maxLength = 0;

for(int i = 0; i < n; i++) {

sum += (nums[i] == 0 ? -1 : 1);

if(map.containsKey(sum)) {

int j = map.get(sum);

maxLength = Math.max(maxLength,i - j);

} else {

map.put(sum,i);

}

}

return maxLength;

}

}

矩陣區(qū)域和

https://leetcode.cn/problems/matrix-block-sum/description/

解析：

這道題目就是二維數(shù)組前綴和的使用

我們先創(chuàng)建好前綴和數(shù)組，然后鎖定求解的區(qū)域，最后計算即可

這里要注意的是前綴和數(shù)組要和我們的最終數(shù)組要一一對應

class Solution {

public int[][] matrixBlockSum(int[][] mat, int k) {

int n = mat.length;

int m = mat[0].length;

int[][] dp = new int[n+1][m+1];

for(int i = 1; i <= n; i++) {

for(int j = 1; j <= m; j++) {

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + mat[i-1][j-1];

}

}

int[][] ans = new int[n][m];

for(int i = 0; i < n; i++) {

for(int j = 0; j < m; j++) {

int r1 = (i - k <= 0 ? 1 : i - k + 1);

int c1 = (j - k <= 0 ? 1 : j - k + 1);

int r2 = (i + k >= n ? n : i + k + 1);

int c2 = (j + k >= m ? m : j + k + 1);

ans[i][j] = dp[r2][c2] - (dp[r1-1][c2] + dp[r2][c1-1] - dp[r1-1][c1-1]);

}

}

return ans;

}

}

柚子快報邀請碼778899分享：算法【Java】 —— 前綴和

http://yzkb.51969.com/

好文閱讀