前綴和 (Prefix Sum)#

很多題目會反覆問「某一段子陣列的總和是多少」。如果每次查詢都從頭加一遍，單次就要 O(n)，查 m 次就是 O(m × n)。前綴和（Prefix Sums）的核心，就是預先把「到每個索引為止的累積和」存下來，讓任意子陣列的和能在 O(1) 取得。這是一種典型的「用空間換時間、把重複計算挪到前置處理」的手法。

核心：累積和與索引邊界#

定義一個前綴和陣列 prefix，讓 prefix[i] 代表「原陣列前 i 個元素的總和」。建議讓 prefix 長度為 n + 1，並令 prefix[0] = 0：

prefix[0] = 0
prefix[i] = a[0] + a[1] + ... + a[i-1]   // 前 i 個元素

有了這張表，任意子陣列 a[i..j]（含兩端、0-based）的和就是：

sum(a[i..j]) = prefix[j + 1] - prefix[i]

多出來的 prefix[0] = 0 不是裝飾，而是讓邊界乾淨的關鍵。有了它，「從 0 開始的子陣列」a[0..j] 也能套同一個公式：prefix[j+1] - prefix[0] = prefix[j+1]，不必為「從頭起算」寫特例。前綴和的 bug 幾乎都出在索引偏移，把長度設成 n + 1、用 prefix[j+1] - prefix[i] 這個固定形狀，最不容易錯。

何時該想到前綴和#

看到這些訊號，就該往前綴和的方向想：

• 出現大量「子陣列和」或「範圍和查詢」（區間反覆被詢問，而原陣列不變）。
• 要**數「和為 k 的子陣列個數」**這類計數問題。
• 任何「某段區間的累積量」——和、計數、甚至累積積——需要被反覆取用。

判斷準則很簡單：若同樣的「累積結果」會被算很多次，就把它預先存起來，之後每次查詢只做一次減法。

基本範例：Range Sum Query ^↗#

給定一個不變的陣列，反覆查詢區間 [i, j] 的和。建表 O(n)、每次查詢 O(1)。

class NumArray(nums: IntArray) {
    private val prefix = IntArray(nums.size + 1)   // 長度 n + 1

    init {
        // prefix[0] = 0 為哨兵，涵蓋從頭起算
        for (i in nums.indices) {
            prefix[i + 1] = prefix[i] + nums[i]
        }
    }

    // 回傳 nums[i..j] 的和（含兩端）
    fun sumRange(i: Int, j: Int): Int = prefix[j + 1] - prefix[i]
}

建表只做一次掃描；之後不論查幾次，每次都是常數時間的一次減法。當查詢次數遠大於 1 時，這個前置處理就賺回來了。

精華：前綴和 + 雜湊表#

前綴和真正的威力，在於和雜湊表結合，解決「和等於 k 的連續子陣列個數 ^↗」。

轉換思路#

子陣列 a[i..j] 的和等於 prefix[j+1] - prefix[i]。要它等於 k，就是要：

prefix[j+1] - prefix[i] = k
=> prefix[i] = prefix[j+1] - k

所以問題從「枚舉所有區間」變成：對每個右端點（當前前綴和 currentSum），找前面出現過幾個前綴和等於 currentSum - k。每找到一個這樣的舊前綴和，就對應到一段和為 k 的子陣列。

用雜湊表邊掃邊數#

我們不需要真的建出整張前綴和陣列，只要一邊掃、一邊用雜湊表記錄「每個前綴和值出現過幾次」即可：

初始要先放入 {0: 1}。這顆「前綴和為 0 出現一次」的種子，對應到 prefix[0] = 0，作用是涵蓋從陣列開頭起算、本身和就等於 k 的子陣列——否則這類答案會被漏數。這正是基本範例裡 prefix[0] = 0 哨兵的同一個觀念。

fun subarraySum(nums: IntArray, k: Int): Int {
    val count = HashMap<Int, Int>()
    count[0] = 1                        // prefix[0] = 0，涵蓋從頭起算的子陣列

    var currentSum = 0
    var result = 0
    for (num in nums) {
        currentSum += num                                    // 走到此處的前綴和
        // 找前面有幾個前綴和等於 currentSum - k
        result += count.getOrDefault(currentSum - k, 0)
        // 把當前前綴和記下來，供右邊的端點查詢
        count[currentSum] = count.getOrDefault(currentSum, 0) + 1
    }
    return result
}

整趟只掃一次、每步是 O(1) 的雜湊操作，總複雜度 O(n) 時間、O(n) 空間；相比暴力枚舉所有區間的 O(n²)，是質的提升。

這跟「兩數之和 ^↗用雜湊找補數」是同一個思路：邊掃描邊把看過的東西丟進雜湊表，對當前元素去查「我需要的那個配對是否已經出現過」。差別只在於這裡查的不是某個數，而是某個前綴和值（補數從 target - num 換成 currentSum - k）。看懂這層對應，這兩類題就合而為一了。延伸閱讀見雜湊表。

延伸：前綴積變體#

同樣的「先把累積量算好」也能用在乘法上。經典題 Product of Array Except Self ^↗：要求 answer[i] 等於「除了自己以外所有元素的乘積」，且不准用除法。

做法是把它拆成左前綴積 × 右後綴積：

• left[i] = a[i] 左邊所有元素的乘積；
• right[i] = a[i] 右邊所有元素的乘積；
• answer[i] = left[i] * right[i]，剛好排除了 a[i] 自己。

只要左、右各掃一遍（甚至可以用一個輸出陣列加一個滾動變數做到 O(1) 額外空間），就能 O(n) 完成。這說明前綴和的思想不限於加法——任何「可累積、可逆推」的運算（和、積……）都能套用。

小結#

前綴和常和雙指標、滑動視窗一起被考慮。原則上：元素全為正、求「最短/最長滿足條件的區間」時，滑動視窗更省空間；但只要陣列可能有負數，視窗無法單調收縮，這時前綴和（搭配雜湊表）才是穩當的解法。