theme: jzman

本文已收錄到 GitHub · AndroidFamily，有 Android 進階知識體系，歡迎 Star。技術和職場問題，請關注公眾號 [彭旭銳] 私信我提問。

前言

大家好，我是小彭。

今天分享到一種非常有趣的資料結構 —— 字首和陣列。字首和的思想本身很容易理解，同時也是理解更高難度的線段樹、字典樹等資料結構的基礎。

那麼，什麼是字首和，我們可以使用字首和解決什麼問題呢？今天我們就圍繞這兩個問題展開。

學習路線圖：

1. 什麼是字首和

字首和陣列是一種用來高效地解決 “靜態資料的頻繁區間和查詢” 問題的資料結構。

先舉個例子，給定一個整數陣列，要求輸出陣列在 $[i, j]$ 區間內元素的總和，這就是區間查詢問題。這道題的暴力解法是很容易想到的，無非就是把 $[i, j]$ 區間中所有元素累計而已即可，時間複雜度是 $O(n)$，空間複雜度是 $O(1)$。

單次查詢確實已經沒有優化空間了，但如果進行頻繁的區間和查詢，很明顯會有非常多重複的求和運算。例如，在查詢 $[1, 5]$ 區間和 $[1, 10]$ 區間時，$[1, 5]$ 這個子區間就被重複計算了。那麼，有可能借助 “空間換時間”，在 $O(1)$ 時間複雜度內計算 $[5000,1000000]$ 上的區間和嗎？

這就需要使用字首和 + 差分技巧：

預處理階段： 開闢一個字首和陣列，記錄每個位置到所有前驅節點的累加和 $preSum$，總共需要 O(n) 時間；
查詢階段： 將區間左右端點的區間和相減，就可以在 $O(1)$ 時間得到這個區間中所有元素的累加和，避免了每次查詢都需要 for 迴圈遍歷整個區間求和。例如，要求 $[i, j]$ 區間的和，就是直接用 $preSum[j + 1] - preSum[i]$ 獲得。

字首和示意圖

2. 典型例題 · 區間和檢索

理解以上概念後，就已經具備解決區間和問題的基本知識了。我們來看一道 LeetCode 上的字首和典型例題：LeetCode 303. 區域和檢索 - 陣列不可變

LeetCode 例題

題解

```kotlin class NumArray(nums: IntArray) {

// 字首和陣列
// 陣列長度加一後不用考慮陣列越界，程式碼更簡潔
private val preSum = IntArray(nums.size + 1) { 0 }

init {
    for (index in nums.indices) {
        preSum[index + 1] = preSum[index] + nums[index]
    }
}

fun sumRange(i: Int, j: Int): Int {
    return preSum[j + 1] - preSum[i]
}

} ```

程式碼很簡單，其中字首和陣列 preSum 的長度要額外加 1 是為了簡化陣列越界判斷。我們來分析它的複雜度：

時間複雜度： 構建字首和陣列的時間複雜度是 $O(n)$，查詢的時間複雜度是 $O(m)$，$n$ 是資料量，$m$ 是區間和查詢的次數；
空間複雜度： $O(n)$，使用了長度為 $n+ 1$ 的字首和陣列。

另外，字首和還適用於二維區間和檢索，思路都是類似的，你可以試試看： LeetCode · 304. 二維區域和檢索 - 矩陣不可變

3. 典型例題 · 字首和 + 雜湊表

繼續看另一道字首和與雜湊表結合的例題：LeetCode 560. 和為 K 的子陣列

LeetCode 例題

這道題就是在考字首和思想，我們可以輕鬆地寫出第一種解法：

題解

```kotlin class Solution { fun subarraySum(nums: IntArray, k: Int): Int { // 1、預處理：構造字首和陣列 var preSum = IntArray(nums.size + 1) { 0 } for (index in nums.indices) { preSum[index + 1] = preSum[index] + nums[index] }

    // 2、列舉所有子陣列，使用「字首和 + 差分」技巧計算區間和
    var result = 0
    for (i in nums.indices) {
        for (j in i until nums.size) {
            val sum_i_j = preSum[j + 1] - preSum[i]
            if (k == sum_i_j) {
                result++
            }
        }
    }
    return result
}

} ```

在這個題解中，我們列舉每個子陣列，使用「字首和 + 差分」技巧計算區間和為 K 的個數，我們來分析下它的複雜度：

時間複雜度： 一共存在 $n^2$ 個子陣列，單次子陣列的區間查詢是 $O(1)$，所以整體的時間複雜度是 $O(n^2)$；
空間複雜度： $O(n)$。

時間複雜度有辦法優化嗎？我們發現，題目要求的是陣列個數，而不關心具體的陣列，所以我們不必列舉全部子陣列（一共有 $n^2$ 個子陣列），我們只需要在計算出當前位置的字首和之後，觀察之前的位置中是否存在字首和正好等於 $preSum[j] - K$ 的位置，有的話，就說明它們之間的區間和就是 $K$。把滿足條件的個數累加起來，就是最終結果。

字首和示意圖

緊接著另一個問題是：怎麼快速找到字首和等於 $preSum[j] - K$ 的位置？聰明的你一定知道了—— 雜湊表。我們可以維護一個雜湊表，記錄字首和出現的位置，就可以用 O(1) 找到它。由於字首和有可能會重複出現，而且我們只關心次數不關心位置，所以對映關係應該為 <字首和 - 出現次數>。

題解

```kotlin class Solution { fun subarraySum(nums: IntArray, k: Int): Int { var preSum = 0 var result = 0

    // 維護雜湊表<字首和，出現次數>
    val map = HashMap<Int, Int>()
    map[0] = 1

    for (index in nums.indices) {
        preSum += nums[index]
        // 獲得字首和為 preSum - k 的出現次數
        val offset = preSum - k
        if (map.contains(offset)) {
            result += map[offset]!!
        }
        map[preSum] = map.getOrDefault(preSum, 0) + 1
    }
    return result
}

} ```

我們來分析下它的複雜度：

時間複雜度： 每個元素只處理一次，整體時間複雜度是 $O(n)$；
空間複雜度： $O(n)$。

4. 典型例題 · 字首和 + 單調佇列

繼續看一道字首和與單調佇列結合的例題，你可以先做一下第 53 題：

LeetCode 例題

在第 53 題中，我們只需要維護一個當前觀察到的最小字首和變數，將其與當前的字首和做差值，就可以得到以當前節點為右端點的最大的區間和。這一題就是考字首和思想，相對簡單。

第 53 題題解

```kotlin class Solution { fun maxSubArray(nums: IntArray): Int { // 字首和 + 單調：維護最小的字首和 var minPreSum = 0 var result = Integer.MIN_VALUE var preSum = 0

    for (element in nums) {
        preSum += element
        result = Math.max(result, preSum - minPreSum)
        minPreSum = Math.min(minPreSum, preSum)
    }
    return result
}

} ```

在第 918 題中，陣列變為環形陣列，環形陣列的問題一般都會用 2 倍的 “假資料長度” 做模擬，求字首和陣列這一步大同小異。

關鍵在於： “子陣列最多隻能包含固定緩衝區 num 中的每個元素一次”，這意味隨著觀察的區間右節點逐漸向右移動，所允許的左區間會限制在一個滑動視窗範圍內，以避免元素重複出現。因此，一個變數不再能夠滿足題目需求。

示意圖

所以我們的問題就是要求這個 “滑動視窗中的最小字首和”。Wait a minute! 滑動視窗的最小值？這不就是使用單調佇列解決 “滑動視窗最大值” 問題這篇文章講的內容嗎，秒懂，單調佇列安排一下。

第 918 題題解

```kotlin class Solution { fun maxSubarraySumCircular(nums: IntArray): Int { val preSum = IntArray(nums.size * 2 + 1).apply { for (index in 0 until nums.size * 2) { this[index + 1] = this[index] + nums[index % nums.size] } }

    // 單調佇列（從隊頭到隊尾遞增）
    val queue = LinkedList<Int>()
    var result = Integer.MIN_VALUE

    for (index in 1 until preSum.size) {
        // if：移除隊頭超出滑動視窗範圍的元素
        // 字首和視窗 k 為 length + 1，比原陣列上的邏輯視窗大 1 位，因為區間的差值要找前一個節點的字首和
        if (!queue.isEmpty() && queue.peekFirst() < index - nums.size /* index - k + 1 */) {
            queue.pollFirst()
        }

        // 從隊頭取目標元素
        result = Math.max(result, preSum[index] - (preSum[queue.peekFirst() ?: 0]))

        // while：隊尾元素大於當前元素，說明隊尾元素不再可能是最小值，後續不再考慮它
        while (!queue.isEmpty() && preSum[queue.peekLast()] >= preSum[index]) {
            // 拋棄隊尾元素
            queue.pollLast()
        }
        queue.offerLast(index)
    }
    return result
}

} ```

我們來分析它的時間複雜度：

時間複雜度： 構建字首和陣列 $O(n)$，字首和陣列中每個元素在單調佇列中入隊和出隊 $1$ 次，因此整體時間複雜度是 $O(n)$;
空間複雜度： 構建字首和陣列 $O(n)$，最壞情況下（遞減序列）所有元素都被新增到單調佇列中，因此整體空間複雜度是 $O(n)$。

提示： 這道題還有使用 Kadane 演算法 的 $O(1)$ 空間複雜度解法。

5. 總結

到這裡，字首和的內容就講完了。文章開頭也提到了， 字首和陣列是一種高效地解決靜態資料的頻繁區間和查詢問題的資料結構，只需要構造一次字首和陣列，就能使用 O(1) 時間完成查詢操作。

那麼，在動態資料的場景中（即動態增加或刪除元素），使用字首和陣列進行區間和查詢是否還保持高效呢？如果不夠高效，有其他的資料結構可以解決嗎？你可以思考以下 2 道題：

更多同類型題目：

| 字首和 | 難度 | 題解 | | --- | --- | --- | | 303. 區間和檢索 - 陣列不可變 | Easy | 【題解】 | | 724. 尋找陣列的中心下標 | Easy | 【題解】 | | 304. 二維區域和檢索 - 矩陣不可變 | Medium | 【題解】 | | 560. 和為 K 的子陣列 | Medium | 【題解】 | | 974. 和可被 K 整除的子陣列 | Medium | 【題解】 | | 1314. 矩陣區域和 | Medium | 【題解】 | | 918. 環形子陣列的最大和 | Medium | 【題解】 | | 525. 連續陣列 | Medium | 【題解】 | | 1248. 統計「優美子陣列」 | Medium | 【題解】 |

本文為稀土掘金技術社群首發簽約文章，14天內禁止轉載，14天后未獲授權禁止轉載，侵權必究！

參考資料

LeetCode 專題 · 字首和 —— LeetCode 出品
LeetCode 題解 · 560. 和為 K 的子陣列 —— liweiwei1419 著
小而美的演算法技巧：字首和陣列 —— labuladong 著
小而美的演算法技巧：差分陣列 —— labuladong 著

使用字首和陣列解決"區間和查詢"問題

theme: jzman

前言

1. 什麼是字首和

2. 典型例題 · 區間和檢索

3. 典型例題 · 字首和 + 雜湊表

4. 典型例題 · 字首和 + 單調佇列

5. 總結