給定整數陣列
nums，實作NumArray類別，支援查詢索引left到right（含）之間的元素總和。sumRange會被多次呼叫。
Example:
Input: [“NumArray”, “sumRange”, “sumRange”, “sumRange”] > [[[-2, 0, 3, -5, 2, -1]], [0, 2], [2, 5], [0, 5]] Output: [null, 1, -1, -3]
Intuition
TIP
核心思路：預處理前綴和陣列 prefix[i] = nums[0] + ... + nums[i-1]，查詢時 sumRange(l, r) = prefix[r+1] - prefix[l]。
- 如果每次查詢都暴力加總，時間為 O(n)，多次查詢效率低
- 前綴和預處理 O(n)，之後每次查詢只要 O(1)
Approaches
1. Brute-Force Sum per Query — Init O(1), Query O(n) / O(1)
- Idea: 每次
sumRange呼叫時遍歷[left, right]區間求和 - Time: 初始化
O(1)，每次查詢O(n) - Space:
O(1)- 不需額外空間
class NumArray(private val nums: IntArray) {
fun sumRange(left: Int, right: Int): Int {
var sum = 0
for (i in left..right) {
sum += nums[i]
}
return sum
}
}⭐ 2. Prefix Sum — Init O(n), Query O(1) / O(n)
- Idea: 預處理前綴和陣列，
prefix[i]代表nums[0..i-1]的總和，查詢時用差值計算 - Time: 初始化
O(n)，每次查詢O(1) - Space:
O(n)- 前綴和陣列
class NumArray(nums: IntArray) {
private val prefix = IntArray(nums.size + 1)
init {
for (i in nums.indices) {
prefix[i + 1] = prefix[i] + nums[i]
}
}
fun sumRange(left: Int, right: Int): Int {
return prefix[right + 1] - prefix[left]
}
}WARNING
前綴和陣列長度為 n + 1，prefix[0] = 0 作為哨兵，避免邊界判斷。
🔑 Takeaways
- Pattern: Prefix Sum 是區間和查詢的基礎資料結構
- Key trick:
prefix多一位（n+1）的設計避免了邊界判斷；此概念可推廣到 2D（LC 304）和帶更新的版本（LC 307，需 BIT/Segment Tree）