Share my short Java code with explanation


  • 0
    M
    /*
        define sum[i][j] --
        sum of all numbers in the rectangle whose top-left point is [0][0], and bot-right point is [i][j].
        
        sumRegion(row0, col0, row1, col1) = 
        sum[row1][col1] + sum[row0 - 1][col0 - 1]
        - sum[row1][col0 - 1] - sum[row0 - 1][col1]
    */
    public class NumMatrix {
    
        int[][] sum;
    
        public NumMatrix(int[][] matrix) {
            if (matrix.length != 0) {
                sum = new int[matrix.length][matrix[0].length];
                for (int i = 0; i < matrix.length; ++i) {
                    int rowSum = 0;
                    for (int j = 0; j < matrix[0].length; ++j) {
                        rowSum += matrix[i][j];
                        sum[i][j] = rowSum + (i < 1 ? 0 : sum[i - 1][j]);
                    }
                }
            }
        }
    
        public int sumRegion(int row1, int col1, int row2, int col2) {
            int up = row1 - 1 < 0 ? 0 : sum[row1 - 1][col2];
            int left = col1 - 1 < 0 ? 0 : sum[row2][col1 - 1];
            int upLeft = row1 - 1 < 0 || col1 - 1 < 0 ? 0 : sum[row1 - 1][col1 - 1];
            return sum[row2][col2] + upLeft - up - left;
        }
    }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.