【Leetcode Daily】304二维区域和检索-矩阵不可变

题目浅析

• 想查看原题可以点击题目链接。

• 简单地说，就是给一个二维数组，给一个区域的起点和终点，求每个区域的数值和。

思路分享

• 具体计算二维前缀和的方式都在参考链接，不多赘述。难点在于区分四种数组的下标，比如 row1 col1 row2 col2，真正要求的数组范围是否需要 + 1，这需要画出来理清楚。

  https://leetcode.cn/problems/range-sum-query-2d-immutable/solutions/2667331/tu-jie-yi-zhang-tu-miao-dong-er-wei-qian-84qp/

代码解答（强烈建议自行解答后再看）

• 参考题解

class NumMatrix:

    def __init__(self, matrix: List[List[int]]):
        m, n = len(matrix), len(matrix[0])
        s = [[0]*(n+1) for _ in range(m+1)]
        for i, row in enumerate(matrix):
            for j, x in enumerate(row):
                s[i+1][j+1] = s[i+1][j] + s[i][j+1] - s[i][j] + x
        self.s = s

    def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
        return self.s[row2+1][col2+1] - self.s[row1][col2+1] - self.s[row2+1][col1] + self.s[row1][col1]


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