304. Range Sum Query 2D - Immutable

二刷 08/2022

Version #1 2D PrefixSum

Time O(MN) for constructor, O(1) for query

Space O(MN)

Runtime: 215 ms, faster than 46.65% of Java online submissions for Range Sum Query 2D - Immutable.

Memory Usage: 127.3 MB, less than 62.68% of Java online submissions for Range Sum Query 2D - Immutable.

class NumMatrix {

    int[][] sums;

    public NumMatrix(int[][] matrix) {

        int rows = matrix.length;

        int cols = matrix[0].length;

        sums = new int[rows][cols];

        for (int y = 0; y < rows; y++) {

            for (int x = 0; x < cols; x++) {

                sums[y][x] = matrix[y][x];

                if (y - 1 >= 0) {

                    sums[y][x] += sums[y - 1][x];

                }

                if (x - 1 >= 0) {

                    sums[y][x] += sums[y][x - 1];

                }

                if (y - 1 >= 0 && x - 1 >= 0) {

                    sums[y][x] -= sums[y - 1][x - 1];

                }

            }

        }

    }

    //   (0,0) (0,1)

    //    -4   -5

    

    public int sumRegion(int row1, int col1, int row2, int col2) {

        //  (row1 - 1, col1 - 1)                     (row1 - 1, col2)

        //                        (row1, col1)       (row1, col2)

        //  (row2, col1 - 1)      (row2, col1)       (row2, col2)

        int sum = sums[row2][col2];

        if (col1 - 1 >= 0) {

            sum -= sums[row2][col1 - 1];

        }

        if (row1 - 1 >= 0) {

            sum -= sums[row1 - 1][col2];

        }

        if (row1 - 1 >= 0 && col1 - 1 >= 0) {

            sum += sums[row1 - 1][col1 - 1];

        }

        return sum;

    }

}

一刷

Version #1 2D PrefixSum

97.29 %
class NumMatrix {

    private int[][] prefixSum;
    private int rows, cols;
    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return;
        this.rows = matrix.length;
        this.cols = matrix[0].length;
        prefixSum = new int[rows + 1][cols + 1];
        // prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1]
        for (int i = 1; i <= rows; i++) {
            for (int j = 1; j <= cols; j++) {
                prefixSum[i][j] = matrix[i - 1][j - 1] + prefixSum[i - 1][j] + prefixSum[i][j - 1] - prefixSum[i - 1][j - 1];
            }
        }
    }
 
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if (rows == 0 || cols == 0) return 0;
        // row2,col1      row2,col2
        // row1,col1      row1,col2
        return prefixSum[row2 + 1][col2 + 1] - prefixSum[row2 + 1][col1] - prefixSum[row1][col2 + 1]
            + prefixSum[row1][col1];
    }
}