今天來聊一道簡單卻十分巧妙的算法問題：算出一共有幾個和為 k 的子數組。

思路很簡單，我把所有子數組都窮舉出來，算它們的和，看看誰的和等于 k 不就行了。

關鍵是，如何快速得到某個子數組的和呢，比如說給你一個數組nums，讓你實現一個接口sum(i, j)，這個接口要返回nums[i..j]的和，而且會被多次調用，你怎么實現這個接口呢？

因為接口要被多次調用，顯然不能每次都去遍歷nums[i..j]，有沒有一種快速的方法在 O(1) 時間內算出nums[i..j]呢？這就需要前綴和技巧了。

一、什么是前綴和

前綴和的思路是這樣的，對于一個給定的數組nums，我們額外開辟一個前綴和數組進行預處理：

這個前綴和數組preSum的含義也很好理解，preSum[i]就是nums[0..i-1]的和。那么如果我們想求nums[i..j]的和，只需要一步操作preSum[j+1]-preSum[i]即可，而不需要重新去遍歷數組了。

回到這個子數組問題，我們想求有多少個子數組的和為 k，借助前綴和技巧很容易寫出一個解法：

int subarraySum(int[] nums, int k) {
    int n = nums.length;
    // 構造前綴和
    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;
    // 窮舉所有子數組
    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;
}

這個解法的時間復雜度空間復雜度，并不是最優(yōu)的解法。不過通過這個解法理解了前綴和數組的工作原理之后，可以使用一些巧妙的辦法把時間復雜度進一步降低。

二、優(yōu)化解法

前面的解法有嵌套的 for 循環(huán)：

第二層 for 循環(huán)在干嘛呢？翻譯一下就是，在計算，有幾個j能夠使得sum[i]和sum[j]的差為 k。毎找到一個這樣的j，就把結果加一。

我們可以把 if 語句里的條件判斷移項，這樣寫：

if (sum[j] == sum[i] - k)
    ans++;

優(yōu)化的思路是：我直接記錄下有幾個sum[j]和sum[i]-k相等，直接更新結果，就避免了內層的 for 循環(huán)。我們可以用哈希表，在記錄前綴和的同時記錄該前綴和出現的次數。

比如說下面這個情況，需要前綴和 8 就能找到和為 k 的子數組了，之前的暴力解法需要遍歷數組去數有幾個 8，而優(yōu)化解法借助哈希表可以直接得知有幾個前綴和為 8。

這樣，就把時間復雜度降到了，是最優(yōu)解法了。

三、總結

前綴和不難，卻很有用，主要用于處理數組區(qū)間的問題。

比如說，讓你統(tǒng)計班上同學考試成績在不同分數段的百分比，也可以利用前綴和技巧：

這樣，給你任何一個分數段，你都能通過前綴和相減快速計算出這個分數段的人數，百分比也就很容易計算了。

但是，稍微復雜一些的算法問題，不止考察簡單的前綴和技巧。比如本文探討的這道題目，就需要借助前綴和的思路做進一步的優(yōu)化，借助哈希表記錄額外的信息?？梢妼︻}目的理解和細節(jié)的分析能力對于算法的優(yōu)化是至關重要的。