​LeetCode刷题实战304：二维区域和检索 - 矩阵不可变

算法的重要性，我就不多说了吧，想去大厂，就必须要经过基础知识和业务逻辑面试+算法面试。所以，为了提高大家的算法能力，这个公众号后续每天带大家做一道算法题，题目就从LeetCode上面选 ！今天和大家聊的问题叫做 二维区域和检索 - 矩阵不可变，我们先来看题面：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) -> 8sumRegion(1, 1, 2, 2) -> 11sumRegion(1, 2, 2, 4) -> 12解题不看官方题解不知道，二维前缀和，了不起了不起。优秀代码时间最优class NumMatrix:def __init__(self, matrix: List[List[int]]):if not matrix:returnm = 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 = matrixdef 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好了，今天的文章就到这里，如果觉得有所收获，请顺手点个在看或者转发吧，你们的支持是我最大的动力 。上期推文：LeetCode1-280题汇总，希望对你有点帮助！LeetCode刷题实战301：删除无效的括号LeetCode刷题实战302：包含全部黑色像素的最小矩阵LeetCode刷题实战303：区域和检索 - 数组不可变