前綴和是什么：

前綴和指一個(gè)數(shù)組的某下標(biāo)之前的所有數(shù)組元素的和（包含其自身）。前綴和分為一維前綴和，以及二維前綴和。前綴和是一種重要的預(yù)處理，能夠降低算法的時(shí)間復(fù)雜度

說個(gè)人話就是比如有一個(gè)數(shù)組：
[1,2,3,4]，然后我求得sum數(shù)組[1,3,6,10];
那我只要有了這個(gè)sum數(shù)組，我就可以在O（1）得時(shí)間內(nèi)求出區(qū)間和，
比如我想求interval[i,j]內(nèi)得區(qū)間和，我怎么辦，我直接那sum[j]-sum[i]就可以了。

ok了解了這個(gè)思想，我們也很容易想到：前綴和得作用或者說前綴和適合解決什么樣的題目呢：就是子數(shù)組，或者字字符串類似的題目：

下面上例題：先從簡(jiǎn)單的開始：

leetcode1732：找到最高海拔：

有一個(gè)自行車手打算進(jìn)行一場(chǎng)公路騎行，這條路線總共由?n + 1?個(gè)不同海拔的點(diǎn)組成。自行車手從海拔為?0?的點(diǎn)?0?開始騎行。

給你一個(gè)長(zhǎng)度為?n?的整數(shù)數(shù)組?gain?，其中?gain[i]?是點(diǎn)?i?和點(diǎn)?i + 1?的?凈海拔高度差（0 <= i < n）。請(qǐng)你返回?最高點(diǎn)的海拔?。

有一個(gè)自行車手打算進(jìn)行一場(chǎng)公路騎行，這條路線總共由?n + 1?個(gè)不同海拔的點(diǎn)組成。自行車手從海拔為?0?的點(diǎn)?0?開始騎行。

給你一個(gè)長(zhǎng)度為?n?的整數(shù)數(shù)組?gain?，其中?gain[i]?是點(diǎn)?i?和點(diǎn)?i + 1?的?凈海拔高度差（0 <= i < n）。請(qǐng)你返回?最高點(diǎn)的海拔?。

class Solution {public int largestAltitude(int[] gain) {int len = gain.length;int[] sum = new int[len+1];for(int i=1;i<=len;++i){sum[i] = gain[i-1]+sum[i-1];}int flag = Integer.MIN_VALUE;for(int i=0;i<=len;++i){if(sum[i]>flag){flag = sum[i];}}return flag;}
}

這道題也算是前綴和的一個(gè)入門，我們求出前綴和數(shù)組sum之后，遍歷sum找到最大值即可。

leetcode 1413 逐步求和得到正數(shù)的最小值：

給你一個(gè)整數(shù)數(shù)組?nums?。你可以選定任意的?正數(shù)?startValue 作為初始值。

你需要從左到右遍歷?nums?數(shù)組，并將 startValue 依次累加上?nums?數(shù)組中的值。

請(qǐng)你在確保累加和始終大于等于 1 的前提下，選出一個(gè)最小的?正數(shù)?作為 startValue 。

輸入：nums = [-3,2,-3,4,2]
輸出：5
解釋：如果你選擇 startValue = 4，在第三次累加時(shí)，和小于 1 。
                累加求和startValue = 4 | startValue = 5 | nums
?                 (4 -3 ) = 1  | (5 -3 ) = 2    |  -3(1 +2 ) = 3  | (2 +2 ) = 4    |   2(3 -3 ) = 0  | (4 -3 ) = 1    |  -3(0 +4 ) = 4  | (1 +4 ) = 5    |   4(4 +2 ) = 6  | (5 +2 ) = 7    |   2

class Solution {public int minStartValue(int[] nums) {int len = nums.length;int[] sum = new int[len+1];for (int i = 1; i <=len; i++) {sum[i] = sum[i-1]+nums[i-1];}int flag = Integer.MAX_VALUE;for (int i = 1; i <=len ; i++) {if(sum[i]<flag){flag = sum[i];}}return flag<0?(flag*-1)+1:1;}
}

這道題就比上一道需要多分析一些東西，

首先題目要求一個(gè)最小的正整數(shù)，所以我們肯定要根據(jù)這個(gè)數(shù)組的和來求。

leetcode 724：找數(shù)組的中心下標(biāo)

給你一個(gè)整數(shù)數(shù)組 nums ，請(qǐng)計(jì)算數(shù)組的 中心下標(biāo) 。
數(shù)組 中心下標(biāo) 是數(shù)組的一個(gè)下標(biāo)，其左側(cè)所有元素相加的和等于右側(cè)所有元素相加的和。
如果中心下標(biāo)位于數(shù)組最左端，那么左側(cè)數(shù)之和視為 0 ，因?yàn)樵谙聵?biāo)的左側(cè)不存在元素。這一點(diǎn)對(duì)于中心下標(biāo)位于數(shù)組最右端同樣適用。
如果數(shù)組有多個(gè)中心下標(biāo)，應(yīng)該返回 最靠近左邊 的那一個(gè)。如果數(shù)組不存在中心下標(biāo)，返回 -1 。

那這道題目不是典型的前綴和嘛，我們要求這個(gè)所謂的中心下標(biāo)，我們不就是這個(gè)中心下標(biāo)的左邊的區(qū)間和==右邊的區(qū)間和嘛

public int pivotIndex(int[] nums) {int len = nums.length;int i;int[] sum = new int[len + 1];sum[0] = 0;for (i = 0; i < len; ++i) {sum[i + 1] = sum[i] + nums[i];}for (i = 1; i < len+1; ++i) {if (sum[len] == (2 * sum[i - 1]) + nums[i-1]) {return i-1;}}return -1;}

當(dāng)我們算出來這個(gè)sum數(shù)組之后，我們只需要從左往右遍歷一下，然后根據(jù)數(shù)學(xué)公式就可以得出下標(biāo)的結(jié)果，

這里有一個(gè)注意點(diǎn)：
就是你求sum數(shù)組的時(shí)候，你需要在sum[0]的位置墊一個(gè)0（這也是前綴和的固定套路），怎么理解呢
比如有一個(gè)數(shù)組：[1,0,0,0],那這個(gè)時(shí)候，1這個(gè)位置很明顯是中心坐標(biāo)，如果你不墊個(gè)0在前面的話，公式就不成立
其實(shí)這種情況也可以作為一個(gè)特判（我認(rèn)為），也可以理解為一個(gè)前綴和的固定套路。

線性前綴和變形：

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

給你一個(gè)整數(shù)數(shù)組?nums，返回?數(shù)組?answer?，其中?answer[i]?等于?nums?中除?nums[i]?之外其余各元素的乘積?。

題目數(shù)據(jù)?保證?數(shù)組?nums之中任意元素的全部前綴元素和后綴的乘積都在??32 位?整數(shù)范圍內(nèi)。

請(qǐng)?不要使用除法，且在?O(n)?時(shí)間復(fù)雜度內(nèi)完成此題。

輸入: nums = [1,2,3,4]
輸出: [24,12,8,6]

先寫一種比較容易想到的方法：

利用對(duì)應(yīng)索引的左側(cè)和右側(cè)（也可以叫前綴和后綴）的乘積來得出答案

舉個(gè)例子：[1,2,3,4]

我們先算出這個(gè)數(shù)組的前綴和數(shù)組和后綴和數(shù)組：

[1,2,6,24]? ?[24,24,12,4]

比如我們要求2這個(gè)下標(biāo)的除自身以外數(shù)組的乘積

我們就可以用前綴和數(shù)組的第一個(gè)元素1，和后綴和數(shù)組的倒二個(gè)元素12相乘，得出12。

class Solution {public int[] productExceptSelf(int[] nums) {int len = nums.length;int[] left = new int[len];left[0] = nums[0];int[] right = new int[len];right[len-1] = nums[len-1];for(int i=1;i<len;++i){left[i] = nums[i]*left[i-1];}for(int i=len-2;i>=0;i--){right[i] = nums[i]*right[i+1];}int[] ans = new int[len];ans[0] = right[1];ans[len-1] = left[len-2];for(int i=1;i<len-1;++i){ans[i] = left[i-1]*right[i+1];}return ans;}
}

?再來一種難一點(diǎn)的方法：

思路就是：

先從上往下算對(duì)應(yīng)索引的左變得乘積，然后再倒上去算對(duì)應(yīng)所以右邊得乘積。

類似有點(diǎn)像上三角和下三角得感覺。

//假如nums為[1,2,3,4]，那么answer的值分別為[(2,3,4),(1,3,4),(1,2,4),(1,2,3)]//如果吧i當(dāng)前值相乘的時(shí)候看做是1那么就有如下樣式//  1, 2, 3, 4 //  1, 1, 3, 4//  1, 2, 1, 4//  1, 2, 3, 1// 他的對(duì)角線1將他們分割成了兩個(gè)三角形，對(duì)于answer的元素，//我們可以先計(jì)算一個(gè)三角形每行的乘積，然后再去計(jì)算另外一個(gè)三角形每行的乘積，//然后各行相乘，就是answer每個(gè)對(duì)應(yīng)的元素

class Solution {public int[] productExceptSelf(int[] nums) {int len = nums.length;int[] left = new int[len];left[0] = 1;for(int i=1;i<len;++i){left[i] = nums[i-1]*left[i-1];}int temp = 1;for(int i=len-1;i>=0;i--){left[i] = left[i]*temp;temp *= nums[i];}return left;}
}

?leetcode 1310：子數(shù)組異或查詢：

有一個(gè)正整數(shù)數(shù)組?arr，現(xiàn)給你一個(gè)對(duì)應(yīng)的查詢數(shù)組?queries，其中?queries[i] = [Li,?Ri]。

對(duì)于每個(gè)查詢?i，請(qǐng)你計(jì)算從?Li?到?Ri?的?XOR?值（即?arr[Li] xor arr[Li+1] xor ... xor arr[Ri]）作為本次查詢的結(jié)果。

并返回一個(gè)包含給定查詢?queries?所有結(jié)果的數(shù)組。

輸入：arr = [1,3,4,8], queries = [[0,1],[1,2],[0,3],[3,3]]
輸出：[2,7,14,8] 
解釋：
數(shù)組中元素的二進(jìn)制表示形式是：
1 = 0001 
3 = 0011 
4 = 0100 
8 = 1000 
查詢的 XOR 值為：
[0,1] = 1 xor 3 = 2 
[1,2] = 3 xor 4 = 7 
[0,3] = 1 xor 3 xor 4 xor 8 = 14 
[3,3] = 8

這道題其實(shí)蠻簡(jiǎn)單，不知道為什么力扣設(shè)置成中等題

這道題有一個(gè)小的注意點(diǎn)，這道題的前綴和數(shù)組的第一個(gè)元素應(yīng)該是多少？

這就要去考慮異或的性質(zhì)了。

1. 兩個(gè)數(shù)異或，相同的位數(shù)等于0 ；0110 ^ 1100 = 1010
2. 一個(gè)數(shù)與0異或，結(jié)果等于本身；
3. 一個(gè)數(shù)異或本身，結(jié)果為0；
4. 綜上，可得第四條性質(zhì)： a ^ b ^ b = a;

所以由異或性質(zhì)得出，前綴和數(shù)組的第一個(gè)數(shù)應(yīng)該是0。

class Solution {public int[] xorQueries(int[] arr, int[][] queries) {int[] xor = new int[arr.length+1];for (int i = 1; i <= arr.length; i++) {xor[i] = xor[i-1] ^ arr[i-1];}int[] ans = new int[queries.length];for (int i = 0; i < queries.length; i++) {ans[i] = xor[queries[i][1]+1] ^ xor[queries[i][0]];}return ans;}
}

leetcode 1829：每個(gè)查詢的最大異或值：

給你一個(gè)?有序?數(shù)組?nums?，它由?n?個(gè)非負(fù)整數(shù)組成，同時(shí)給你一個(gè)整數(shù)?maximumBit?。你需要執(zhí)行以下查詢?n?次：

1. 找到一個(gè)非負(fù)整數(shù)?k < 2的maximumBit次方?，使得?nums[0] XOR nums[1] XOR ... XOR nums[nums.length-1] XOR k?的結(jié)果?最大化?。k?是第?i?個(gè)查詢的答案。
2. 從當(dāng)前數(shù)組?nums?刪除?最后?一個(gè)元素。

請(qǐng)你返回一個(gè)數(shù)組?answer?，其中?answer[i]是第?i?個(gè)查詢的結(jié)果。

輸入：nums = [0,1,1,3], maximumBit = 2
輸出：[0,3,2,3]
解釋：查詢的答案如下：
第一個(gè)查詢：nums = [0,1,1,3]，k = 0，因?yàn)?0 XOR 1 XOR 1 XOR 3 XOR 0 = 3 。
第二個(gè)查詢：nums = [0,1,1]，k = 3，因?yàn)?0 XOR 1 XOR 1 XOR 3 = 3 。
第三個(gè)查詢：nums = [0,1]，k = 2，因?yàn)?0 XOR 1 XOR 2 = 3 。
第四個(gè)查詢：nums = [0]，k = 3，因?yàn)?0 XOR 3 = 3 。

這道題和上一道題差不多，都是異或類型的前綴和，

這一題需要多考慮的一個(gè)條件就是這個(gè)k的大小，題目說k小于2的maximumBit次方，我們由異或的性質(zhì)可以知道，我們要想最后的結(jié)果盡可能大，我們希望我們異或的對(duì)象的1盡可能的多。

知道這個(gè)條件之后，這題就很簡(jiǎn)單了，我們只需要把我們累異或的結(jié)果都和這個(gè)最大值進(jìn)行異或就行。

class Solution {public int[] getMaximumXor(int[] nums, int maximumBit) {int flag = (1 << maximumBit) - 1;int[] ans = new int[nums.length];int k = 0;for(int i=0;i<nums.length;i++){k ^= nums[i];ans[nums.length-1-i] = flag ^ k;}return ans;}
}

線性前綴和統(tǒng)計(jì)：

leetcode 523:連續(xù)的子數(shù)組和：

給你一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?k?，編寫一個(gè)函數(shù)來判斷該數(shù)組是否含有同時(shí)滿足下述條件的連續(xù)子數(shù)組：

• 子數(shù)組大小?至少為 2?，且
• 子數(shù)組元素總和為?k?的倍數(shù)。

如果存在，返回?true?；否則，返回?false?。

如果存在一個(gè)整數(shù)?n?，令整數(shù)?x?符合?x = n * k?，則稱?x?是?k?的一個(gè)倍數(shù)。0?始終視為?k?的一個(gè)倍數(shù)

輸入：nums = [23,2,4,6,7], k = 6
輸出：true
解釋：[2,4] 是一個(gè)大小為 2 的子數(shù)組，并且和為 6 。

先貼一個(gè)我一開始寫的超時(shí)解法：

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int[] sum = new int[nums.length+1];int i,j;if(nums.length==1){return false;}if(nums.length==2){int temp = nums[0]+nums[1];return temp%k==0?true:false;}for(i=1;i<=nums.length;++i){sum[i] += nums[i-1] + sum[i-1];}for(i=0;i< nums.length-1;++i){for(j=(i+2);j<= nums.length;++j){if((sum[j]-sum[i])%k==0){return true;}}}return false;}
}

很明顯這是一個(gè)n方的解法。

下面貼正確解法：

首先在做這個(gè)題目之前，我們需要去明白一個(gè)數(shù)學(xué)關(guān)系：

預(yù)處理前綴和數(shù)組 sum，方便快速求得某一段區(qū)間的和。然后假定 [i,j] 是我們的目標(biāo)區(qū)間，那么有：

sum[j]?sum[i?1]=n?ksum[j] - sum[i - 1] = n * k
sum[j]?sum[i?1]=n?k
經(jīng)過簡(jiǎn)單的變形可得：

sum[j]/k? -? sum[i-1]/k? =? n

要使得兩者除 k 相減為整數(shù)，需要滿足 sum[j] 和 sum[i?1]對(duì) k取余相同。

（這個(gè)就是我看題解看到的數(shù)學(xué)關(guān)系）下面是證明：

知道了這一層數(shù)學(xué)關(guān)系之后，我們的思路就變成了：

先開一個(gè)哈希表。

我們從前綴和數(shù)組i=2的情況開始遍歷，我們把sum[i-2]%k的這個(gè)余數(shù)存在哈希表中，

我們每次遍歷一個(gè)元素，就去查這個(gè)哈希表中是否有和我們這個(gè)余數(shù)相同的數(shù)。

這其實(shí)和經(jīng)典題目?jī)蓴?shù)之和有點(diǎn)像了。

class Solution {public boolean checkSubarraySum(int[] nums, int k) {int len = nums.length;int[] sum = new int[len+1];Set<Integer> table = new HashSet<>();for(int i=1;i<=len;++i){sum[i] += sum[i-1] + nums[i-1];}int flag = 0;for(int i=2;i<=len;++i){flag = sum[i-2]%k;table.add(flag);if(table.contains(sum[i]%k)){return true;}}return false;}
}

leetcode 1508:子數(shù)組和排序后的區(qū)間和：

給你一個(gè)數(shù)組?nums?，它包含?n?個(gè)正整數(shù)。你需要計(jì)算所有非空連續(xù)子數(shù)組的和，并將它們按升序排序，得到一個(gè)新的包含?n * (n + 1) / 2?個(gè)數(shù)字的數(shù)組。

請(qǐng)你返回在新數(shù)組中下標(biāo)為?left?到?right?（下標(biāo)從 1 開始）的所有數(shù)字和（包括左右端點(diǎn)）。由于答案可能很大，請(qǐng)你將它對(duì) 10^9 + 7 取模后返回。

輸入：nums = [1,2,3,4], n = 4, left = 1, right = 5
輸出：13 
解釋：所有的子數(shù)組和為 1, 3, 6, 10, 2, 5, 9, 3, 7, 4 。將它們升序排序后，我們得到新的數(shù)組 [1, 2, 3, 3, 4, 5, 6, 7, 9, 10] 。下標(biāo)從 le = 1 到 ri = 5 的和為 1 + 2 + 3 + 3 + 4 = 13 。

這題其實(shí)沒有什么技巧，就是一道前綴和的模擬題，我們先求一下前綴和數(shù)組，然后開一個(gè)長(zhǎng)度為n * (n + 1) / 2?個(gè)數(shù)字的數(shù)組，對(duì)前綴和數(shù)組遍歷，把每個(gè)子數(shù)組的和給求出來，然后排序，最后輸出即可。

class Solution {int mod = 1000000007;public int rangeSum(int[] nums, int n, int left, int right) {int[] sum = new int[n+1];int i,j;for(i=1;i<=n;++i){sum[i] = sum[i-1] + nums[i-1];}int[] ans = new int[(n*(n+1))/2];int index = 0;for(i=1;i<=n;++i){for(j=i;j<=n;++j){ans[index++] = sum[j] - sum[i-1];}}Arrays.sort(ans);int result = 0;for(i=left-1;i<right;++i){result += ans[i];result = result%mod;}return result;}
}

這里說一個(gè)小坑：

就是最后這個(gè)result數(shù)據(jù)的處理：

我一開始是

        Arrays.sort(ans);int result = 0;for(i=left-1;i<right;++i){result += ans[i]%mod;}return result;

這樣寫有什么問題呢，那個(gè)ans[i]會(huì)先做取余操作，然后再 + ，就會(huì)導(dǎo)致后面的結(jié)果溢出。

改成 result = （result + ans[i] )%mod 和 result += ans[i];? result = result%mod;都行。

leetcode 1423：可連續(xù)的最大點(diǎn)數(shù)

幾張卡牌?排成一行，每張卡牌都有一個(gè)對(duì)應(yīng)的點(diǎn)數(shù)。點(diǎn)數(shù)由整數(shù)數(shù)組?cardPoints?給出。

每次行動(dòng)，你可以從行的開頭或者末尾拿一張卡牌，最終你必須正好拿?k?張卡牌。

你的點(diǎn)數(shù)就是你拿到手中的所有卡牌的點(diǎn)數(shù)之和。

給你一個(gè)整數(shù)數(shù)組?cardPoints?和整數(shù)?k，請(qǐng)你返回可以獲得的最大點(diǎn)數(shù)。

輸入：cardPoints = [1,2,3,4,5,6,1], k = 3
輸出：12
解釋：第一次行動(dòng)，不管拿哪張牌，你的點(diǎn)數(shù)總是 1 。但是，先拿最右邊的卡牌將會(huì)最大化你的可獲得點(diǎn)數(shù)。最優(yōu)策略是拿右邊的三張牌，最終點(diǎn)數(shù)為 1 + 6 + 5 = 12 。

思路：

這題應(yīng)該怎么想呢？或者說我們?cè)趺赐熬Y和那個(gè)方面想呢？

我們知道前綴和解決的是連續(xù)子數(shù)組或者子字符串的問題，我們?cè)倏催@個(gè)題目，題目說我們抽牌可以從前面抽，也可以從后面抽，那這個(gè)數(shù)組就不一定是連續(xù)的了，

這個(gè)時(shí)候我們就需要逆向思維一下。

我們想要抽出來的牌最大，那就是剩下的牌最小，我們抽牌的數(shù)組不一定連續(xù)，不過剩下來的數(shù)組一定是連續(xù)的，所以我們的思路就是去求剩下來的牌的最小值。

具體來說：

我們要抽k張牌，就是要剩下（len-k）張牌，所以我們可以維護(hù)一個(gè)（len-k）張牌的滑動(dòng)窗口。

我們一開始直接把這個(gè)滑動(dòng)窗口填滿，然后再開始遍歷這個(gè)數(shù)組，不斷更新這個(gè)連續(xù)子數(shù)組的最小值即可。

這里說一個(gè)題外話，為什么要先填滿滑動(dòng)窗口，其實(shí)我一開始的做法不是先填滿，是遍歷完了（len-k）個(gè)元素之后再遍歷剩下的元素，不過我感覺這樣下標(biāo)處理起來好麻煩。

class Solution {public int maxScore(int[] cardPoints, int k) {int len = cardPoints.length;int[] sum = new int[len+1];int i,cur = 0,min = Integer.MAX_VALUE;int flag = len-k;for(i=1;i<=len;++i){sum[i] = cardPoints[i-1] + sum[i-1];}for(i=0;i<flag;++i){cur += cardPoints[i];}for(i=flag;i<=len;++i){cur = Math.min(cur,sum[i]-sum[i-flag]);}return sum[len]-cur;}
}

leetcode 1685:有序數(shù)值中差絕對(duì)值之和：

給你一個(gè)?非遞減?有序整數(shù)數(shù)組?nums?。

請(qǐng)你建立并返回一個(gè)整數(shù)數(shù)組?result，它跟?nums?長(zhǎng)度相同，且result[i]?等于?nums[i]?與數(shù)組中所有其他元素差的絕對(duì)值之和。

換句話說，?result[i]?等于?sum(|nums[i]-nums[j]|)?，其中?0 <= j < nums.length?且?j != i?（下標(biāo)從 0 開始）。

輸入：nums = [2,3,5]
輸出：[4,3,5]
解釋：假設(shè)數(shù)組下標(biāo)從 0 開始，那么
result[0] = |2-2| + |2-3| + |2-5| = 0 + 1 + 3 = 4，
result[1] = |3-2| + |3-3| + |3-5| = 1 + 0 + 2 = 3，
result[2] = |5-2| + |5-3| + |5-5| = 3 + 2 + 0 = 5。

思路：

根據(jù)這個(gè)例子很容易想到我們可以一種解法：

比如我們要找nums[i]==3這個(gè)情況下的result，我們可以用nums[i]*len - sum[len-1]，

代碼：

class Solution {public int[] getSumAbsoluteDifferences(int[] nums) {int sum = 0;int i;for(i=0;i< nums.length;++i){sum += nums[i];}int[] result = new int[nums.length];for(i=0;i< nums.length;++i){result[i] = Math.abs((nums[i]* nums.length)-sum);}return result;}
}

我們很快就會(huì)發(fā)現(xiàn)是錯(cuò)誤的，因?yàn)檫@題算的是絕對(duì)值，

按原來的算法，我們用nums[i]*len - sum[len-1] 得出：3*3-10然后取絕對(duì)值，

這樣算出來的值是1，不過答案是3，問題就是3-2是＞0的，而3-5是＜，分開取絕對(duì)值的和是3，而我們直接把這兩個(gè)數(shù)合在一起算了。

解決辦法是：

我們觀察到這個(gè)數(shù)組是有序的，所以我們可以分段進(jìn)行求，并且利用前綴和數(shù)組進(jìn)行優(yōu)化，

class Solution {public int[] getSumAbsoluteDifferences(int[] nums) {int[] sum = new int[nums.length];int len = nums.length;int i,j;sum[0] = nums[0];for(i=1;i< nums.length;++i){sum[i] = sum[i-1] + nums[i];}int[] result = new int[len];for(i=0;i<len;++i){result[i] = ((i+1)*nums[i]-sum[i]) + (sum[len-1]-sum[i]-(len-i-1)*nums[i]);}return result;}
}

leetcode 2155:分組得分最高的所有下標(biāo)：

給你一個(gè)下標(biāo)從?0?開始的二進(jìn)制數(shù)組?nums?，數(shù)組長(zhǎng)度為?n?。nums?可以按下標(biāo)?i（?0 <= i <= n?）拆分成兩個(gè)數(shù)組（可能為空）：numsleft?和?numsright?。

• numsleft?包含?nums?中從下標(biāo)?0?到?i - 1?的所有元素（包括?0?和?i - 1?），而?numsright?包含?nums?中從下標(biāo)?i?到?n - 1?的所有元素（包括?i?和?n - 1?）。
• 如果?i == 0?，numsleft?為?空?，而?numsright?將包含?nums?中的所有元素。
• 如果?i == n?，numsleft?將包含?nums?中的所有元素，而?numsright?為?空?。

下標(biāo)?i?的?分組得分?為?numsleft?中?0?的個(gè)數(shù)和?numsright?中?1?的個(gè)數(shù)之?和?。

返回?分組得分 最高?的?所有不同下標(biāo)?。你可以按?任意順序?返回答案。

輸入：nums = [0,0,1,0]
輸出：[2,4]
解釋：按下標(biāo)分組
- 0 ：numsleft 為 [] 。numsright 為 [0,0,1,0] 。得分為 0 + 1 = 1 。
- 1 ：numsleft 為 [0] 。numsright 為 [0,1,0] 。得分為 1 + 1 = 2 。
- 2 ：numsleft 為 [0,0] 。numsright 為 [1,0] 。得分為 2 + 1 = 3 。
- 3 ：numsleft 為 [0,0,1] 。numsright 為 [0] 。得分為 2 + 0 = 2 。
- 4 ：numsleft 為 [0,0,1,0] 。numsright 為 [] 。得分為 3 + 0 = 3 。
下標(biāo) 2 和 4 都可以得到最高的分組得分 3 。
注意，答案 [4,2] 也被視為正確答案。

思路：

我一開始想的思路是：求出前綴和數(shù)組，因?yàn)檫@個(gè)數(shù)組中只有0和1，所以，我們只要有了前綴和數(shù)組，我們可以通過下標(biāo)的關(guān)系很快得出0和1的個(gè)數(shù)，也就是這個(gè)時(shí)候的分?jǐn)?shù)。

class Solution {public List<Integer> maxScoreIndices(int[] nums) {int len = nums.length;int[] sum = new int[len+1];for(int i=1;i<=len;++i){sum[i] = sum[i-1] + nums[i-1];}List<Integer> ans = new ArrayList<>();int score = -1;ans.add(score);int temp = 0;for(int i=0;i<=len;++i){temp = Math.abs(sum[i]-(i+1)) + sum[len] - sum[i];if(temp>score){ans.clear();ans.add(i);score = temp;} else if (temp==score) {ans.add(i);}}return ans;}
}

更好的思路：

這里其實(shí)可以利用到一點(diǎn)貪心的想法，我們要想讓這個(gè)分?jǐn)?shù)盡可能大，其實(shí)就讓左半邊盡可能有多的0。

class Solution {public List<Integer> maxScoreIndices(int[] nums) {int len = nums.length;int maxscore = 0;int preSum = 0;List<Integer> ans = new ArrayList<>();ans.add(0);for(int i=0;i<len;++i){if(nums[i]==0){preSum++;if(preSum>maxscore){ans.clear();ans.add(i+1);maxscore = preSum;} else if (preSum==maxscore) {ans.add(i+1);}}else preSum--;}return ans;}
}

?這里有一個(gè)小細(xì)節(jié)就是我們要在列表之前先墊一個(gè)0，我們可以想象：[1,1]這個(gè)數(shù)組，里面沒有一個(gè)0，如果我們不墊這個(gè)0，答案就什么都沒有。

leetcode 2222 選擇建筑的方案數(shù)：

給你一個(gè)下標(biāo)從?0?開始的二進(jìn)制字符串?s?，它表示一條街沿途的建筑類型，其中：

• s[i] = '0'?表示第?i?棟建筑是一棟辦公樓，
• s[i] = '1'?表示第?i?棟建筑是一間餐廳。

作為市政廳的官員，你需要隨機(jī)?選擇?3 棟建筑。然而，為了確保多樣性，選出來的 3 棟建筑?相鄰?的兩棟不能是同一類型。

• 比方說，給你?s = "001101"?，我們不能選擇第?1?，3?和?5?棟建筑，因?yàn)榈玫降淖有蛄惺?"011"?，有相鄰兩棟建筑是同一類型，所以?不合?題意。

請(qǐng)你返回可以選擇 3 棟建筑的?有效方案數(shù)?。

輸入：s = "001101"
輸出：6
解釋：
以下下標(biāo)集合是合法的：
- [0,2,4] ，從 "001101" 得到 "010"
- [0,3,4] ，從 "001101" 得到 "010"
- [1,2,4] ，從 "001101" 得到 "010"
- [1,3,4] ，從 "001101" 得到 "010"
- [2,4,5] ，從 "001101" 得到 "101"
- [3,4,5] ，從 "001101" 得到 "101"
沒有別的合法選擇，所以總共有 6 種方法。

思路：

這題和之前的前綴和題目有些不同，這道題更多是用了前綴和的思想。

對(duì)任意一個(gè)位置，以它為中心構(gòu)建合法相鄰建筑的數(shù)量，分兩種情況討論：

該位置左側(cè)1的數(shù)量*該位置右側(cè)1的數(shù)量 （若該位置為0 ）。這樣可以構(gòu)成101。
該位置左側(cè)0的數(shù)量*該位置右側(cè)0的數(shù)量 （若該位置為1 ）。這樣可以構(gòu)成010。

一般前綴和得前綴和數(shù)組求得是某一個(gè)位置元素前面得和。

這道題求的是某一個(gè)位置前面1或者0的數(shù)量。

?具體算法思路：

• 先從右往左遍歷一次數(shù)組，算出對(duì)應(yīng)位置右側(cè)0或者1的數(shù)量（這個(gè)位置如果是0，就算1的數(shù)量，相反也一樣）
• 再從左往右遍歷一次數(shù)組，算出對(duì)應(yīng)位置的方案數(shù)（因?yàn)槲覀冞@個(gè)時(shí)候已經(jīng)有右側(cè)對(duì)應(yīng)的0和1的數(shù)量，這個(gè)時(shí)候的zeroCount和oneCount分別對(duì)應(yīng)左側(cè)的0和1的數(shù)量，我們直接相乘即可得出這個(gè)位置上的方案數(shù)）

class Solution {public long numberOfWays(String s) {int len = s.length();int[] count = new int[len];char[] str = s.toCharArray();long ans = 0;int i;int oneCount = 0;int zeroCount = 0;//從右往左遍歷，統(tǒng)計(jì)每個(gè)位置右側(cè)0或者1的數(shù)量for(i=len-1;i>=0;i--){if(str[i]=='0'){count[i] = oneCount;}else count[i] = zeroCount;oneCount += str[i]=='1'?1:0;zeroCount += str[i]=='0'?1:0;}oneCount = 0; zeroCount = 0;//從左往右遍歷，根據(jù)count數(shù)組算出每個(gè)位置對(duì)應(yīng)的方案數(shù)for(i=0;i<len;++i){if(str[i]=='0'){count[i] *= oneCount;}else count[i] *= zeroCount;oneCount += str[i]=='1'?1:0;zeroCount += str[i]=='0'?1:0;ans += count[i];}return ans;}
}

線性前綴和+哈希表：

在做這個(gè)專題的題目之前，我覺得得先復(fù)習(xí)一下經(jīng)典的一道題目：兩數(shù)之和：

class Solution {public int[] twoSum(int[] nums, int target) {Map <Integer,Integer> table = new HashMap<>();table.put(nums[0],0);for(int i=1;i<nums.length;++i){if(table.containsKey(target-nums[i])){int[] ans = new int[2];ans[0] = table.get(target-nums[i]);ans[1] = i;return ans;}table.put(nums[i],i);}return new int[2];}
}

我感覺在做前綴和和哈希表的題目中總是有兩數(shù)之和這道題目的影子

兩數(shù)之和這道題用了哈希表求在一個(gè)集合中是否有我們需要的目標(biāo)值。

而在做前綴和的題目中用哈希表更像是在集合中找我們需要的區(qū)間段。

因?yàn)槲覀冎?#xff0c;前綴和就是用來解決子數(shù)組的問題?

下面上例題：

leetcode 930. 和相同的二元子數(shù)組：

給你一個(gè)二元數(shù)組?nums?，和一個(gè)整數(shù)?goal?，請(qǐng)你統(tǒng)計(jì)并返回有多少個(gè)和為?goal?的?非空?子數(shù)組。

子數(shù)組?是數(shù)組的一段連續(xù)部分。

輸入：nums = [1,0,1,0,1], goal = 2
輸出：4
解釋：
有 4 個(gè)滿足題目要求的子數(shù)組：[1,0,1]、[1,0,1,0]、[0,1,0,1]、[1,0,1]

class Solution {public int numSubarraysWithSum(int[] nums, int t) {int len = nums.length;Map<Integer,Integer> map = new HashMap<>();map.put(0,1);int[] sum = new int[len+1];int i,j;int ans = 0;for(i=1;i<=len;++i){sum[i] = sum[i-1] + nums[i-1];}for(i=0;i<len;++i){int tar = sum[i+1] - t;if(map.containsKey(tar)){ans += map.get(tar);}map.put(sum[i+1],map.getOrDefault(sum[i+1],0)+1);}return ans;}
}

?兩數(shù)之和中的哈希表存儲(chǔ)的是：數(shù)組的值和索引

而這道題存儲(chǔ)的是：前綴和數(shù)組的值和出現(xiàn)的次數(shù)

leetcode560： 和為K的子數(shù)組：

class Solution {public int subarraySum(int[] nums, int k) {if (nums.length == 0) {return 0;}HashMap<Integer,Integer> map = new HashMap<>();//細(xì)節(jié)，這里需要預(yù)存前綴和為 0 的情況，會(huì)漏掉前幾位就滿足的情況//例如輸入[1,1,0]，k = 2 如果沒有這行代碼，則會(huì)返回0,漏掉了1+1=2，和1+1+0=2的情況//輸入：[3,1,1,0] k = 2時(shí)則不會(huì)漏掉//因?yàn)閜resum[3] - presum[0]表示前面 3 位的和，所以需要map.put(0,1),墊下底map.put(0, 1);int count = 0;int presum = 0;for (int x : nums) {presum += x;//當(dāng)前前綴和已知，判斷是否含有 presum - k的前綴和，那么我們就知道某一區(qū)間的和為 k 了。if (map.containsKey(presum - k)) {count += map.get(presum - k);//獲取次數(shù)}//更新map.put(presum,map.getOrDefault(presum,0) + 1);}return count;}
}

?這道題就和上一道幾乎一模一樣，哈希表的存儲(chǔ)的都是前綴和數(shù)組的值和出現(xiàn)的次數(shù)。

leetcode 1248：統(tǒng)計(jì)優(yōu)美子數(shù)組：?

給你一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?k。如果某個(gè)連續(xù)子數(shù)組中恰好有?k?個(gè)奇數(shù)數(shù)字，我們就認(rèn)為這個(gè)子數(shù)組是「優(yōu)美子數(shù)組」。

請(qǐng)返回這個(gè)數(shù)組中?「優(yōu)美子數(shù)組」?的數(shù)目。

輸入：nums = [1,1,2,1,1], k = 3
輸出：2
解釋：包含 3 個(gè)奇數(shù)的子數(shù)組是 [1,1,2,1] 和 [1,2,1,1] 。

這道題其實(shí)沒有用到前綴和數(shù)組，不過用到了前綴和的思想。

前綴和數(shù)組表示數(shù)組下標(biāo)之前的數(shù)組元素的和

這道題用了前綴和的思想，我們不是去統(tǒng)計(jì)數(shù)組元素的和

而是統(tǒng)計(jì)數(shù)組下標(biāo)之前的奇數(shù)數(shù)字的個(gè)數(shù)。

做完這道題之后，我感覺對(duì)前綴和思想的理解深入了一點(diǎn)，之前有一道題，leetcode2222也用了前綴和的思想，這道題統(tǒng)計(jì)的是數(shù)組下標(biāo)之前0或者1元素的個(gè)數(shù)。那個(gè)時(shí)候理解起來好別扭，可能是對(duì)這個(gè)前綴和數(shù)組的理解不對(duì)，認(rèn)為做這種題目都需要去求這個(gè)前綴和數(shù)組。

?

class Solution {public int numberOfSubarrays(int[] nums, int k) {int len = nums.length;HashMap<Integer,Integer> map = new HashMap<>();//哈希表記錄的是前綴區(qū)間中的奇數(shù)個(gè)數(shù)map.put(0,1);int ans = 0;int oddnum = 0;int i,j;for(i=0;i<len;++i){oddnum += nums[i] & 1;if(map.containsKey(oddnum-k)){ans += map.get(oddnum-k);}map.put(oddnum,map.getOrDefault(oddnum,0)+1);}return ans;}
}

?leetcode 974：和可被K整除的子數(shù)組：

給定一個(gè)整數(shù)數(shù)組?nums?和一個(gè)整數(shù)?k?，返回其中元素之和可被?k?整除的（連續(xù)、非空）?子數(shù)組?的數(shù)目。

子數(shù)組?是數(shù)組的?連續(xù)?部分。

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

其實(shí)寫了三個(gè)題目了，已經(jīng)就是有感覺了，這道題和前幾道題有什么不同呢？特別是和為K的子數(shù)組，

在和為K的子數(shù)組中，我們的判斷條件是：是否含有sum[i] - k的前綴和

而在這一題中，我們的判斷條件是：是否含有sum[i] %k相同的前綴和。

知道了這一點(diǎn)之后，這題就和之前的題目差不多了。

class Solution {public int subarraysDivByK(int[] nums, int k) {int len = nums.length;HashMap<Integer,Integer> map = new HashMap<>();map.put(0,1);int i,j;int ans = 0;int[] sum = new int[len+1];for(i=1;i<=len;++i){sum[i] = sum[i-1] + nums[i-1];}for(i=0;i<len;++i){int key = (sum[i+1] % k + k) % k;if(map.containsKey(key)){ans += map.get(key);}map.put(key,map.getOrDefault(key,0)+1);}return ans;}
}

?注意點(diǎn)：

我們看到上面代碼中有一段代碼是這樣的

int key = (presum % K + K) % K;
這是為什么呢？不能直接用 presum % k 嗎？

這是因?yàn)楫?dāng)我們 presum 為負(fù)數(shù)時(shí)，需要對(duì)其糾正。糾正前(-1) %2 = (-1)，糾正之后 ( (-1) % 2 + 2) % 2=1 保存在哈希表中的則為 1.則不會(huì)漏掉部分情況，例如輸入為 [-1,2,9],K = 2如果不對(duì)其糾正則會(huì)漏掉區(qū)間 [2] 此時(shí) 2 % 2 = 0，符合條件，但是不會(huì)被計(jì)數(shù)。

我覺得這個(gè)取余的方法也可以記下來，用來處理一些碰到負(fù)數(shù)取余的情況。

差分：

差分可以看成前綴和的逆運(yùn)算

詳細(xì)差分算法理解看這個(gè)博客：前綴和與差分 圖文并茂 超詳細(xì)整理（全網(wǎng)最通俗易懂）-CSDN博客

我們稍微對(duì)比一下前綴和和差分的例子，來理解一下這兩個(gè)概念：

前綴和的作用很清楚了：

如果我們要求一個(gè)數(shù)組中某一段區(qū)間的數(shù)組和，我們用前綴和就可以在O（1）的時(shí)間內(nèi)查找出來。

而差分呢？

我們想象一個(gè)場(chǎng)景：我們有一個(gè)數(shù)組，我們要在規(guī)定的區(qū)間 [l,r] 這個(gè)區(qū)間內(nèi)＋c ，我們同樣得遍歷，如果我們需要做n次這樣的操作，那時(shí)間復(fù)雜度就很高了。

所以差分?jǐn)?shù)組就是用來解決這個(gè)問題的。

對(duì) c[l]+=v：由于差分是前綴和的逆向過程，這個(gè)操作對(duì)于將來的查詢而言，帶來的影響是對(duì)于所有的下標(biāo)大于等于 l?的位置都增加了值 v；
對(duì) c[r+1]?=v：由于我們期望只對(duì) [l,r] 產(chǎn)生影響，因此需要對(duì)下標(biāo)大于 r 的位置進(jìn)行減值操作，從而抵消“影響”。

?最后我們?cè)儆们熬Y和的運(yùn)算來輸出結(jié)果即可。

leetcode 1109 航班預(yù)定統(tǒng)計(jì)：

這里有?n?個(gè)航班，它們分別從?1?到?n?進(jìn)行編號(hào)。

有一份航班預(yù)訂表?bookings?，表中第?i?條預(yù)訂記錄?bookings[i] = [firsti, lasti, seatsi]?意味著在從?firsti?到?lasti?（包含?firsti?和?lasti?）的?每個(gè)航班?上預(yù)訂了?seatsi?個(gè)座位。

請(qǐng)你返回一個(gè)長(zhǎng)度為?n?的數(shù)組?answer，里面的元素是每個(gè)航班預(yù)定的座位總數(shù)。

輸入：bookings = [[1,2,10],[2,3,20],[2,5,25]], n = 5
輸出：[10,55,45,25,25]
解釋：
航班編號(hào)        1   2   3   4   5
預(yù)訂記錄 1 ：   10  10
預(yù)訂記錄 2 ：       20  20
預(yù)訂記錄 3 ：       25  25  25  25
總座位數(shù)：      10  55  45  25  25
因此，answer = [10,55,45,25,25]

這道題就是典型的差分題，

我們遍歷bookings數(shù)組，對(duì)數(shù)組中[l,r]區(qū)間加上對(duì)應(yīng)的位置。

在（r，len）再減去對(duì)應(yīng)的位置，達(dá)到平衡。

最后求出前綴和。

class Solution {public int[] corpFlightBookings(int[][] bs, int n) {int[] diff = new int[n+2];for(int[] b:bs){diff[b[0]] += b[2];diff[b[1]+1] -= b[2];}int[] ans = new int[n];ans[0] = diff[1];for(int i=1;i<n;++i){ans[i] = ans[i-1]+diff[i+1];}return ans;}
}