前綴和技巧：解決子數(shù)組問題

今天來聊一道簡單卻十分巧妙的算法問題：算出一共有幾個和為 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]呢？這就需要前綴和技巧了。

一、什么是前綴和

前綴和的思路是這樣的，對于一個給定的數(shù)組nums，我們額外開辟一個前綴和數(shù)組進(jìn)行預(yù)處理：

這個前綴和數(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ù)雜度空間復(fù)雜度，并不是最優(yōu)的解法。不過通過這個解法理解了前綴和數(shù)組的工作原理之后，可以使用一些巧妙的辦法把時間復(fù)雜度進(jìn)一步降低。

二、優(yōu)化解法

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

第二層 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ù)。

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

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

三、總結(jié)

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

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

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

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