146ms by storing the sum of current column


  • 0
    C

    When using the sum of the [0,0] to [i,j], the TLE will occur. So I decrease the time of preprocessing by summarizing the column num.

    public class NumMatrix {
    
        int[][] sums;
    
        public NumMatrix(int[][] matrix) {
            if (matrix.length == 0) {
                return;
            }
            this.sums = new int[matrix.length + 1][matrix[0].length];
    
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[0].length; j++) {
                    sums[i + 1][j] = sums[i][j] + matrix[i][j];
                }
            }
        }
    
        public int sumRegion(int row1, int col1, int row2, int col2) {
            int sum = 0;
            for(int i = col1; i <= col2; i++) {
                sum += sums[row2 + 1][i] - sums[row1][i];
            }
            return sum;
        }
    }
    

    but with this way, time is 146ms.

    How to do to get the time less?


Log in to reply
 

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