20210302 304. 二维区域和检索 – 矩阵不可变

题目

https://leetcode-cn.com/problems/range-sum-query-2d-immutable/

题解

1。利用一维数组前缀和

我们以前做过求任意一个一维数组的子序列和,这次变成二维的了,可以先求一维数组的和,然后每一行遍历累加matrix为原数组,subResult为一维数组的前缀和数组

public NumMatrix(int[][] matrix) {
if(matrix.length==0){
return;
}
this.matrix = matrix;
subResult = new int[matrix.length][matrix[0].length];
for (int i = 0; i < subResult.length; i++) {
int result = 0;
for (int j = 0; j < subResult[0].length; j++) {
result += matrix[i][j];
subResult[i][j] = result;
}
}
}

public int sumRegion(int row1, int col1, int row2, int col2) {
int result = 0;
for (int i = row1; i <= row2; i++) {
result += subResult[i][col2] - subResult[i][col1] + matrix[i][col1];
}
return result;
}

2。 二维数组前缀和

https://leetcode-cn.com/problems/range-sum-query-2d-immutable/solution/ru-he-qiu-er-wei-de-qian-zhui-he-yi-ji-y-6c21/

其中有个小技巧和我们求一维数组子序列和一样,可以对subResult数组行和列多加1,可以减少一些if边界判断。

发表评论

邮箱地址不会被公开。 必填项已用*标注