【题解】力扣304. 二维区域和检索 - 矩阵不可变

题目来源

二维区域和检索 - 矩阵不可变

思路

方法一

一维前缀和

创建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];
}

参考来源

1. 官方题解
2. 宫水三叶