Python solution


  • 1
    Z

    Calculate a 2D sum matrix, so that the matrix can be divided into

    A B

    C D

    The return value is D-B-C+A

    def __init__(self, matrix):
        if not matrix:
            self.sum2D = []
        else:
            m,n = len(matrix), len(matrix[0])
            self.sum2D = matrix[:]
            for i in range(m):
                for j in range(1,n):
                    self.sum2D[i][j] = self.sum2D[i][j-1] + matrix[i][j]
    
            for j in range(n):
                for i in range(1,m):
                    self.sum2D[i][j] = self.sum2D[i-1][j] + self.sum2D[i][j]
    
    def sumRegion(self, row1, col1, row2, col2):
        if not self.sum2D:
            return 0
        res = self.sum2D[row2][col2]
        if row1 > 0: res -= self.sum2D[row1-1][col2]
        if col1 > 0: res -= self.sum2D[row2][col1-1]
        if row1 > 0 and col1 > 0: res += self.sum2D[row1-1][col1-1]
        return res

Log in to reply
 

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