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

难度: 🌕

问题描述

---

解法 1 - 一维前缀和

class NumMatrix {
    // 思路：
    // 保存一个方向的前缀和 - 例 水平方向
    int[][] board;

    public NumMatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        board = new int[row][col + 1];
        for(int i = 0; i < row; i ++) {
            for(int j = 0; j < col; j ++) {
                board[i][j + 1] = board[i][j] + matrix[i][j];
            }
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        // 求每行的和 然后累加
        int res = 0;
        for(int i = row1; i <= row2; i ++) {
            res += board[i][col2 + 1] - board[i][col1];
        }
        return res;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

---

输出 1

---

解法 2 - 二维前缀和

class NumMatrix {
    // 思路：
    // 二维前缀和
    // 可以看出矩形的面积，当前矩形面积 == 总面积 - 上方矩形 - 左方矩形 + 左上角矩形面积
    int[][] board;

    public NumMatrix(int[][] matrix) {
        int row = matrix.length;
        int col = matrix[0].length;
        board = new int[row + 1][col + 1];
        for(int i = 1; i <= row; i ++) {
            for(int j = 1; j <= col; j ++) {
                board[i][j] = board[i - 1][j] + board[i][j - 1] - board[i - 1][j - 1] + matrix[i - 1][j - 1];
                // 上方矩形 + 左方矩形 - 重合左上角矩形 + 当前值
            }
            // System.out.println(Arrays.toString(board[i]));
        }
    }
    
    public int sumRegion(int row1, int col1, int row2, int col2) {
        return board[row2 + 1][col2 + 1] - board[row1][col2 + 1] - board[row2 + 1][col1] + board[row1][col1];
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

---

输出 2