前缀和 03

6FmqOO.png

思路：

方法一：暴力

模拟一遍就可以了，java勉强能过，5%而已。

class NumMatrix {

    private int[][] grid;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        grid = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                grid[i][j] = matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        int sum = 0;
        for (int i = row1; i <= row2; i++) {
            for (int j = col1; j <= col2; j++) {
                sum += grid[i][j];
            }
        }
        return sum;
    }
}

方法三：二维前缀和

第一点，初始化前缀和数组，根据下图原理从左上角一直遍历到右下角，完成初始化

image

\operatorname{preSum}[i+1][j+1]=\operatorname{preSum}[i][j+1]+\operatorname{preSum}[i+1][j]-\operatorname{preSum}[i][j]+\operatorname{matrix}[i][j]

第二点，根据前缀和数组来求任意子矩阵面积

image

\text { preSum }[\text { row } 2][\text { col } 2]-\text { preSum }[\text { row } 2][\operatorname{col} 1-1]-\text { preSum }[\text { row } 1-1][\text { col } 2]+\text { preSum }[\text { row } 1-1][\operatorname{col} 1-1]

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

public class NumMatrix {

    private int[][] preSum;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0) return;
        int m = matrix.length;
        int n = matrix[0].length;
        preSum = new int[m + 1][n + 1]; // 表示矩阵区域 (0,0)->(m,n) 元素总和
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                preSum[i + 1][j + 1] = preSum[i][j + 1] + preSum[i + 1][j] - preSum[i][j] + matrix[i][j];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2 + 1][col2 + 1] - preSum[row1][col2 + 1] - preSum[row2 + 1][col1] + preSum[row1][col1];
    }

}