今天和大家聊的问题叫做 二维区域和检索 - 矩阵不可变，我们先来看题面：https://leetcode-cn.com/problems/range-sum-query-2d-immutable/
示例
给定 matrix = [ [3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5] ] sumRegion(2, 1, 4, 3) -> 8 sumRegion(1, 1, 2, 2) -> 11 sumRegion(1, 2, 2, 4) -> 12
解题
不看官方题解不知道，二维前缀和，了不起了不起。
优秀代码
时间最优
class NumMatrix: def __init__(self, matrix: List[List[int]]): if not matrix: return m = len(matrix) n = len(matrix[0]) self.p = [[0] * (n+1) for _ in range(m+1)] for i in range(1, m+1): for j in range(1, n+1): self.p[i][j] = matrix[i-1][j-1] + self.p[i-1][j] + self.p[i][j-1] - self.p[i-1][j-1] def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int: return self.p[row2+1][col2+1] - self.p[row1][col2+1] - self.p[row2+1][col1] + self.p[row1][col1]
空间最优
class NumMatrix: def __init__(self, matrix: List[List[int]]): self._matrix = matrix def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int: result = 0 """ for row in self._matrix[row1:row2+1]: for col in row[col1:col2+1]: result += col """ for i in range(row1, row2+1): for j in range(col1, col2+1): result += self._matrix[i][j] return result
好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。
