Description
給定 2D 矩陣
matrix，設計一個類別NumMatrix，支援查詢子矩陣(row1, col1)到(row2, col2)的元素和。sumRegion會被多次呼叫。
Example:
Input: matrix = [[3,0,1,4,2],[5,6,3,2,1],[1,2,0,1,5],[4,1,0,1,7],[1,0,3,0,5]] sumRegion(2,1,4,3) = 8
Intuition#
核心思路：預計算 2D 前綴和矩陣，查詢時用容斥原理（Inclusion-Exclusion）O(1) 算出任意子矩陣的和。
prefix[i][j]= 從(0,0)到(i-1,j-1)的矩形元素和- 查詢
(r1,c1)到(r2,c2)的和：prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1] - 預處理 O(m*n)，每次查詢 O(1)
Approaches#
1: Brute Force (每次查詢遍歷)#
- 概念: 每次
sumRegion都遍歷子矩陣的所有元素求和 - 時間複雜度: 初始化
O(1)，查詢O(m * n)最壞 - 空間複雜度:
O(1)- 不需額外空間
class NumMatrix(private val matrix: Array<IntArray>) {
fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
var sum = 0
for (r in row1..row2) {
for (c in col1..col2) {
sum += matrix[r][c]
}
}
return sum
}
}⭐2: 2D Prefix Sum#
- 概念: 預計算 2D 前綴和，查詢時用容斥原理 O(1) 計算
- 時間複雜度: 初始化
O(m * n)，查詢O(1) - 空間複雜度:
O(m * n)- 前綴和矩陣
class NumMatrix(matrix: Array<IntArray>) {
private val prefix: Array<IntArray>
init {
val m = matrix.size
val n = matrix[0].size
prefix = Array(m + 1) { IntArray(n + 1) }
for (r in 1..m) {
for (c in 1..n) {
prefix[r][c] = matrix[r - 1][c - 1] +
prefix[r - 1][c] + prefix[r][c - 1] - prefix[r - 1][c - 1]
}
}
}
fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
return prefix[row2 + 1][col2 + 1] -
prefix[row1][col2 + 1] -
prefix[row2 + 1][col1] +
prefix[row1][col1]
}
}容斥原理圖示：要求區域 D 的和，用「大矩形 - 上方 - 左方 + 左上角（被減兩次）」。前綴和矩陣多一行一列（padding），避免邊界判斷。
🔑 Takeaways#
- Pattern: 2D 區間查詢 -> 2D 前綴和 + 容斥原理
- 關鍵技巧: 前綴和矩陣加 padding（大小
(m+1) x (n+1)）簡化邊界處理；容斥公式prefix[r2+1][c2+1] - prefix[r1][c2+1] - prefix[r2+1][c1] + prefix[r1][c1]要熟記