LeetCode 筆記 - 304. Range Sum Query 2D - Immutable
題目在此 304. Range Sum Query 2D - Immutable
給定一個 2D matrix,請根據給定的矩形範圍計算出舉行總和

解題思維
這題我們要用 Prefix Sum 來幫助我們
如果沒寫過他的基本題,建議可以先從 303. Range Sum Query - Immutable 這裡開始
基本概念很簡單,先建立起 2D 的 Prefix Sum Table
每個 x
, y
代表的是從 matrix[0][0] 到 matrix[y][x] 形成的矩形總和
所以如果我們想要白色那塊矩形的總和,那就會是
如下圖所示

程式碼
1 | class NumMatrix: |
也許你也會想看看
- LeetCode 筆記 - 303. Range Sum Query - Immutable
- LeetCode 筆記 - 307.Range Sum Query - Mutable
- LeetCode 筆記 - 29. Divide Two Integers
0%