<span>【题解】力扣304. 二维区域和检索 - 矩阵不可变</span>
题目来源
思路
方法一
一维前缀和
创建m行，n+1列的二位前缀和数组
class NumMatrix {
int sum[][];
public NumMatrix(int[][] matrix) {
int r = matrix.length;
int c = matrix[0].length;
sum = new int[r][c+1];
for(int i = 0;i<r;i++){
for(int j = 0;j<c;j++){
sum[i][j+1] = sum[i][j]+matrix[i][j];
}
}
}
public int sumRegion(int row1, int col1, int row2, int col2) {
int ans = 0;
for(int i = row1;i<=row2;i++){
ans += sum[i][col2+1] - sum[i][col1];
}
return ans;
}
}
/**
* Your NumMatrix object will be instantiated and called as such:
* NumMatrix obj = new NumMatrix(matrix);
* int param_1 = obj.sumRegion(row1,col1,row2,col2);
*/
复杂度分析：
- 时间复杂度：O(mn)
- 空间复杂度：O(mn)
方法二
二维前缀和
如图：
二维前缀和数组中的每一个格子，比如f[i][j]，就是从（i，j）为右下角，（0，0）为左上角，这一个区域内的数字总和。
预设二维前缀和的第0行和第0列都为0，如上图所示，可以求出二维前缀和数组的每一个位置。
int n = matrix.length;
int m = matrix[0].length;
sum = new int[n + 1][m + 1];
// 预处理除前缀和数组（模板部分）
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
求出二维前缀和数组后，当我们要求\((x_1,y_1)\)作为左上角，\((x_2,y_2)\)作为右下角的区域和的时候，可以直接利用前缀和数组快速求解。如下图所示。
由于原数组的下标是从0开始的，因此，在用二维前缀和数组计算的时候，要在给定的原数组的坐标基础上加1
public int sumRegion(int x1, int y1, int x2, int y2) {
// 但由于我们源数组下标从 0 开始，因此要在模板的基础上进行 + 1
x1++; y1++; x2++; y2++;
return f[x2][y2] - f[x1 - 1][y2] - f[x2][y1 - 1] + f[x1 - 1][y1 - 1];
}
