LeetCode 筆記 - 304. Range Sum Query 2D - Immutable

題目在此 304. Range Sum Query 2D - Immutable

給定一個 2D matrix,請根據給定的矩形範圍計算出舉行總和

image 55

解題思維

這題我們要用 Prefix Sum 來幫助我們
如果沒寫過他的基本題,建議可以先從 303. Range Sum Query - Immutable 這裡開始

基本概念很簡單,先建立起 2D 的 Prefix Sum Table
每個 x, y 代表的是從 matrix[0][0] 到 matrix[y][x] 形成的矩形總和

所以如果我們想要白色那塊矩形的總和,那就會是

Prefix Sum Table [y][x]
-
Prefix Sum Table [y][x - 1]
-
Prefix Sum Table [y - 1][x1]
+
Prefix Sum Table [y - 1][x1 - 1]

如下圖所示

image 56

程式碼

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class NumMatrix:

def __init__(self, matrix: List[List[int]]):

self.y = len(matrix)
self.x = len(matrix[0])

self.count_map = collections.defaultdict(int)

for y in range(self.y):
count = 0
for x in range(self.x):
count += matrix[y][x]
self.count_map[(y, x)] = self.count_map[(y - 1, x)] + count

def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.count_map[(row2, col2)] - self.count_map[(row1 - 1, col2)] - self.count_map[(row2, col1 - 1)] + self.count_map[(row1 - 1, col1 - 1)]

也許你也會想看看