【3.2】LeetCode每日一题·二维区域和检索 - 矩阵不可变

2021年03月02日 12时15分

标签： LeetCode 数组前缀和

## 题目描述
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 `(row1, col1)`，右下角为`(row2, col2)`。
(img)
上图子矩阵左上角`(row1, col1) = (2, 1)`，右下角`(row2, col2) = (4, 3)`，该子矩形内元素的总和为`8`。

#### 示例
	给定 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
	sumRegion(1, 1, 2, 2) -> 11
	sumRegion(1, 2, 2, 4) -> 12

#### 提示
	你可以假设矩阵不可变。
	会多次调用 sumRegion 方法。
	你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

#### 来源
> 来源：力扣（LeetCode）
> 链接：[题目链接](https://leetcode-cn.com/problems/range-sum-query-2d-immutable/ "题目链接")

## 解题思路
和昨天的题一样，只是昨天的题目是数组的区间求和（一维），这里是矩阵的子矩阵求和（二维）。同样考虑到

```math
\displaystyle
\sum_{x=row1}^{row2}\sum_{y=col1}^{col2}matrix[x][y]
=\sum_{x=0}^{row2}\sum_{y=0}^{col2}matrix[x][y] 
-\sum_{x=0}^{row1-1}\sum_{y=0}^{col2}matrix[x][y]
```
```math
\displaystyle
- \sum_{x=0}^{row2}\sum_{y=0}^{col1-1}matrix[x][y]
+ \sum_{x=0}^{row1-1}\sum_{y=0}^{col1-1}matrix[x][y]
```

因此我们首先在$$O(NM)$$（$$N, M$$分别代表矩阵的高和宽）时间内预处理出矩阵的二维前缀和

```math
\displaystyle
diff[i][j]=\sum_{x=0}^{i}\sum_{y=0}^{j}matrix[x][y]
```

然后需要查询区间和时，使用$$O(1)$$的时间利用四个前缀和计算答案即可。
Tips：注意数组越界。

##代码
	class NumMatrix {
	public:
		vector<vector<int>> diff;
		NumMatrix(vector<vector<int>>& matrix) {
			vector<int> temp;
			for(int i = 0; i < matrix.size(); i++){
				for(int j = 0; j < matrix[0].size(); j++){
					temp.push_back((i-1>=0? diff[i-1][j]: 0)+(j-1>=0? temp[j-1]: 0)-(i-1>=0&&j-1>=0? diff[i-1][j-1]: 0)+matrix[i][j]);
				}
				diff.push_back(temp);
				temp.clear();
			}
		}

int sumRegion(int row1, int col1, int row2, int col2) {
			return diff[row2][col2]-(col1-1>=0? diff[row2][col1-1]: 0) - (row1-1>=0? diff[row1-1][col2]: 0) + (row1-1>=0&&col1-1>=0? diff[row1-1][col1-1]: 0);
		}
	};

/**
	 * Your NumMatrix object will be instantiated and called as such:
	 * NumMatrix* obj = new NumMatrix(matrix);
	 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
	 */

## 用时和内存
> 执行用时：16 ms，在所有 C++提交中击败了98.55%的用户
> 内存消耗：15MB，在所有 C++提交中击败了70.50%的用户

所有评论

暂无评论

新增评论

邮箱

邮箱仅作验证使用

图形验证码

邮箱验证码

目录

【3.2】LeetCode每日一题·二维区域和检索 - 矩阵不可变

所有评论

暂无评论

新增评论