讀完本文胶哲，你可以去力扣拿下如下題目：
-----------
今天來聊一道簡單卻十分巧妙的算法問題：算出一共有幾個和為 k 的子數(shù)組陡叠。
那我把所有子數(shù)組都窮舉出來，算它們的和身隐，看看誰的和等于 k 不就行了。
關(guān)鍵是，如何快速得到某個子數(shù)組的和呢，比如說給你一個數(shù)組 nums丁稀，讓你實現(xiàn)一個接口 sum(i, j)，這個接口要返回 nums[i..j] 的和倚聚，而且會被多次調(diào)用线衫，你怎么實現(xiàn)這個接口呢？
因為接口要被多次調(diào)用惑折，顯然不能每次都去遍歷 nums[i..j]授账，有沒有一種快速的方法在 O(1) 時間內(nèi)算出 nums[i..j] 呢？這就需要前綴和技巧了惨驶。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)白热，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄粗卜，持續(xù)更新屋确。建議收藏，按照我的文章順序刷題休建，掌握各種算法套路后投再入題海就如魚得水了乍恐。
一、什么是前綴和
前綴和的思路是這樣的测砂，對于一個給定的數(shù)組 nums茵烈，我們額外開辟一個前綴和數(shù)組進(jìn)行預(yù)處理：
int n = nums.length;
// 前綴和數(shù)組
int[] preSum = new int[n + 1];
preSum[0] = 0;
for (int i = 0; i < n; i++)
preSum[i + 1] = preSum[i] + nums[i];
這個前綴和數(shù)組 preSum 的含義也很好理解，preSum[i] 就是 nums[0..i-1] 的和砌些。那么如果我們想求 nums[i..j] 的和呜投，只需要一步操作 preSum[j+1]-preSum[i] 即可，而不需要重新去遍歷數(shù)組了存璃。
回到這個子數(shù)組問題仑荐，我們想求有多少個子數(shù)組的和為 k，借助前綴和技巧很容易寫出一個解法：
int subarraySum(int[] nums, int k) {
int n = nums.length;
// 構(gòu)造前綴和
int[] sum = new int[n + 1];
sum[0] = 0;
for (int i = 0; i < n; i++)
sum[i + 1] = sum[i] + nums[i];
int ans = 0;
// 窮舉所有子數(shù)組
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
// sum of nums[j..i-1]
if (sum[i] - sum[j] == k)
ans++;
return ans;
}
這個解法的時間復(fù)雜度 O(N^2) 空間復(fù)雜度 O(N)纵东，并不是最優(yōu)的解法粘招。不過通過這個解法理解了前綴和數(shù)組的工作原理之后，可以使用一些巧妙的辦法把時間復(fù)雜度進(jìn)一步降低偎球。
二洒扎、優(yōu)化解法
前面的解法有嵌套的 for 循環(huán)：
for (int i = 1; i <= n; i++)
for (int j = 0; j < i; j++)
if (sum[i] - sum[j] == k)
ans++;
第二層 for 循環(huán)在干嘛呢？翻譯一下就是衰絮，在計算袍冷，有幾個 j 能夠使得 sum[i] 和 sum[j] 的差為 k。毎找到一個這樣的 j猫牡，就把結(jié)果加一胡诗。
我們可以把 if 語句里的條件判斷移項，這樣寫：
if (sum[j] == sum[i] - k)
ans++;
優(yōu)化的思路是：我直接記錄下有幾個 sum[j] 和 sum[i] - k 相等，直接更新結(jié)果煌恢，就避免了內(nèi)層的 for 循環(huán)骇陈。我們可以用哈希表，在記錄前綴和的同時記錄該前綴和出現(xiàn)的次數(shù)瑰抵。
int subarraySum(int[] nums, int k) {
int n = nums.length;
// map：前綴和 -> 該前綴和出現(xiàn)的次數(shù)
HashMap<Integer, Integer>
preSum = new HashMap<>();
// base case
preSum.put(0, 1);
int ans = 0, sum0_i = 0;
for (int i = 0; i < n; i++) {
sum0_i += nums[i];
// 這是我們想找的前綴和 nums[0..j]
int sum0_j = sum0_i - k;
// 如果前面有這個前綴和缩歪，則直接更新答案
if (preSum.containsKey(sum0_j))
ans += preSum.get(sum0_j);
// 把前綴和 nums[0..i] 加入并記錄出現(xiàn)次數(shù)
preSum.put(sum0_i,
preSum.getOrDefault(sum0_i, 0) + 1);
}
return ans;
}
比如說下面這個情況，需要前綴和 8 就能找到和為 k 的子數(shù)組了谍憔，之前的暴力解法需要遍歷數(shù)組去數(shù)有幾個 8，而優(yōu)化解法借助哈希表可以直接得知有幾個前綴和為 8主籍。
這樣习贫，就把時間復(fù)雜度降到了 O(N)，是最優(yōu)解法了千元。
PS：我認(rèn)真寫了 100 多篇原創(chuàng)苫昌，手把手刷 200 道力扣題目，全部發(fā)布在 labuladong的算法小抄幸海，持續(xù)更新祟身。建議收藏，按照我的文章順序刷題物独，掌握各種算法套路后投再入題海就如魚得水了袜硫。
三、總結(jié)
前綴和不難挡篓，卻很有用婉陷，主要用于處理數(shù)組區(qū)間的問題。
比如說官研，讓你統(tǒng)計班上同學(xué)考試成績在不同分?jǐn)?shù)段的百分比秽澳，也可以利用前綴和技巧：
int[] scores; // 存儲著所有同學(xué)的分?jǐn)?shù)
// 試卷滿分 150 分
int[] count = new int[150 + 1]
// 記錄每個分?jǐn)?shù)有幾個同學(xué)
for (int score : scores)
count[score]++
// 構(gòu)造前綴和
for (int i = 1; i < count.length; i++)
count[i] = count[i] + count[i-1];
這樣，給你任何一個分?jǐn)?shù)段戏羽，你都能通過前綴和相減快速計算出這個分?jǐn)?shù)段的人數(shù)担神，百分比也就很容易計算了。
但是始花，稍微復(fù)雜一些的算法問題妄讯，不止考察簡單的前綴和技巧。比如本文探討的這道題目衙荐，就需要借助前綴和的思路做進(jìn)一步的優(yōu)化捞挥，借助哈希表去除不必要的嵌套循環(huán)∮且鳎可見對題目的理解和細(xì)節(jié)的分析能力對于算法的優(yōu)化是至關(guān)重要的砌函。
希望本文對你有幫助。
＿＿＿＿＿＿＿＿＿＿＿＿＿
我的 在線電子書 有 100 篇原創(chuàng)文章，手把手帶刷 200 道力扣題目讹俊，建議收藏垦沉！對應(yīng)的 GitHub 算法倉庫 已經(jīng)獲得了 70k star，歡迎標(biāo)星仍劈！
