题目描述
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (row1, col1) ，右下角为 (row2, col2) 。
上图子矩阵左上角 (row1, col1) = (2, 1) ，右下角(row2, col2) = (4, 3)，该子矩形内元素的总和为 8。
示例：
给定 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
提示：
你可以假设 row1 ≤ row2 且 col1 ≤ col2 。
解题思路
依然沿用前缀和的思路, 只不过由一维扩展到了二维.
使用一个二维数组记录前缀和, 由于是二维数组, 这里的前缀和f(i, j)定义为(0, 0)到(i, j)子矩阵的所有元素之和. 那么在计算前缀和时, 还是需要使用动态规划的方法.
在求f(i, j)之前, 我们已经知道了f(i-1, j-1), f(i-1, j), f(i, j-1)的值, 为了覆盖所有方格, 先求f(i-1, j)和f(i, j-1)之和, 但由于加了两次f(i-1, j-1)部分, 需要减去一次f(i-1, j-1)部分, 最后再加上新的matrix(i, j)的值. 因此状态转移公式如下图中所示.
得到前缀和之后, 就要考虑求解大矩阵中任意位置的子矩阵元素之和的问题. 如下图所示, 求点A到点D确定的子矩形中所有元素之和记为S(A, D), 那么S(A, D)就要从S(O, D)中来. 为了减去红色和粉红色的部分, 就要将S(O, D)减去S(O, E)再减去S(O, F). 由于灰色部分减去了两次, 所以要加上一次S(O, G).
公式如下:
S(A, D) = S(O, G) - S(O, E) - S(O, F) + S(O, G)
另外还有一点需要特别注意. 如果点D的坐标有一个维度为0, 问题就由二维问题降为一维问题, 这种边界情况在计算前缀和以及求解任意两点的结果时都需要考虑. 而同一维的情况一样, 在创建前缀和矩阵时, 在左侧和上方的外围都添加上一圈0, 这样就将所有问题都转化为矩阵内部的问题, 也就不用考虑边缘情况了.
对比使用与不使用这个技巧的代码复杂度.
不使用:
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
self.matrix_prefix = None
n, m = None, None
if matrix:
n = len(matrix)
if n:
m = len(matrix[0])
if n and m:
self.matrix_prefix = [[0] * m for _ in range(n)]
self.matrix_prefix[0][0] = matrix[0][0]
for i in range(1, n):
self.matrix_prefix[i][0] = self.matrix_prefix[i - 1][0] + matrix[i][0]
for j in range(1, m):
self.matrix_prefix[0][j] = self.matrix_prefix[0][j - 1] + matrix[0][j]
for i in range(1, n):
for j in range(1, m):
self.matrix_prefix[i][j] = self.matrix_prefix[i][j - 1] + \
self.matrix_prefix[i - 1][j] - \
self.matrix_prefix[i - 1][j - 1] + \
matrix[i][j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
if self.matrix_prefix is None:
return 0
if row1 == 0 and col1 == 0:
return self.matrix_prefix[row2][col2]
if row1 == 0:
return self.matrix_prefix[row2][col2] - self.matrix_prefix[row2][col1 - 1]
if col1 == 0:
return self.matrix_prefix[row2][col2] - self.matrix_prefix[row1 - 1][col2]
return self.matrix_prefix[row2][col2] - \
self.matrix_prefix[row1 - 1][col2] - \
self.matrix_prefix[row2][col1 - 1] + \
self.matrix_prefix[row1 - 1][col1 - 1]
使用:
class NumMatrix:
def __init__(self, matrix: List[List[int]]):
if not matrix or not matrix[0]:
M, N = 0, 0
else:
M, N = len(matrix), len(matrix[0])
self.preSum = [[0] * (N + 1) for _ in range(M + 1)]
for i in range(M):
for j in range(N):
self.preSum[i + 1][j + 1] = self.preSum[i][j + 1] + self.preSum[i + 1][j] - self.preSum[i][j] + matrix[i][j]
def sumRegion(self, row1: int, col1: int, row2: int, col2: int) -> int:
return self.preSum[row2 + 1][col2 + 1] - self.preSum[row2 + 1][col1] - self.preSum[row1][col2 + 1] + self.preSum[row1][col1]
相关题目
