求解思路
这道题可以这样理解：
就像一维数组可以通过前缀和快速计算区间和一样,二维矩阵也可以预处理出每个位置到左上角(0,0)的矩形区域和,这样查询任意矩形区域时只需要用类似容斥原理的方式,通过四个角的前缀和做加减运算就能O(1)得到结果。
具体来说：
我们创建一个比原矩阵大一圈的前缀和数组sum,其中sum[i][j]表示从(0,0)到(i-1,j-1)的矩形区域和,
构建时利用已经计算好的左边和上边的前缀和,加上当前元素,再减去重复计算的左上角区域即可;
查询时,目标区域的和等于右下角的前缀和减去上边和左边多余的部分,再加回被减了两次的左上角部分。
完整代码实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
|
class NumMatrix {
public int[][] sum; // 前缀和数组,sum[i][j]表示从(0,0)到(i-1,j-1)的矩形区域和
public NumMatrix(int[][] matrix) {
int n = matrix.length; // 矩阵行数
int m = matrix[0].length; // 矩阵列数
// 创建(n+1)×(m+1)的前缀和数组,多一行一列方便处理边界
sum = new int[n + 1][m + 1];
// 先将原矩阵的值复制到sum数组中,索引偏移1
for (int a = 1, c = 0; c < n; a++, c++) {
for (int b = 1, d = 0; d < m; b++, d++) {
sum[a][b] = matrix[c][d];
}
}
// 计算二维前缀和
// sum[i][j] = 当前元素 + 左边的前缀和 + 上边的前缀和 - 左上角的前缀和(被加了两次需要减去)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
}
}
}
public int sumRegion(int a, int b, int c, int d) {
// 将查询坐标转换为前缀和数组的坐标(右下角+1)
c++;
d++;
// 利用容斥原理计算矩形区域和:
// 右下角前缀和 - 上边多余部分 - 左边多余部分 + 左上角重复减去的部分
return sum[c][d] - sum[c][b] - sum[a][d] + sum[a][b];
}
}
|
如果觉得有帮助，欢迎点赞、关注、转发~