LC 304. 二维区域和检索 - 矩阵不可变

题目描述

这是 LeetCode 上的 304. 二维区域和检索 - 矩阵不可变 ,难度为 中等

给定一个二维矩阵,计算其子矩形范围内元素的总和,该子矩阵的左上角为 (row1, col1) ,右下角为 (row2, col2) 。

上图子矩阵左上角 (row1, col1) = (2, 1) ,右下角(row2, col2) = (4, 3),该子矩形内元素的总和为 8。

示例:

1
2
3
4
5
6
7
8
9
10
11
给定 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

提示:

  • 你可以假设矩阵不可变。
  • 会多次调用 sumRegion 方法。
  • 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。

前缀和解法(二维)

真就是今天的「每日一题」呗 ~

这是一道「二维前缀和」的裸题。

「二维前缀和」解决的是二维矩阵中的矩形区域求和问题。

二维前缀和数组中的每一个格子记录的是「以当前位置为区域的右下角(区域左上角恒定为原数组的左上角)的区域和」

贴一张官解示意图,我觉得很清晰:

1.png

如果觉得不清晰,请将将 f[i][j] 理解成是以 (i, j) 为右下角,(0, 0) 为左上角的区域和。

因此当我们要求 (x1, y1) 作为左上角,(x2, y2) 作为右下角 的区域和的时候,可以直接利用前缀和数组快速求解:

sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1]

再贴官解示意图(画图困难户在学做图了,别骂😢):

(x1, y1) == (row1, col1),(x2, y2) == (row2, col2)

image.png

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class NumMatrix {
int[][] sum;
public NumMatrix(int[][] matrix) {
int n = matrix.length, m = n == 0 ? 0 : matrix[0].length;
// 与「一维前缀和」一样,前缀和数组下标从 1 开始,因此设定矩阵形状为 [n + 1][m + 1](模板部分)
sum = new int[n + 1][m + 1];
// 预处理除前缀和数组(模板部分)
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}

public int sumRegion(int x1, int y1, int x2, int y2) {
// 求某一段区域和 [i, j] 的模板是 sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];(模板部分)
// 但由于我们源数组下标从 0 开始,因此要在模板的基础上进行 + 1
x1++; y1++; x2++; y2++;
return sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}
}

  • 时间复杂度:预处理前缀和数组需要对原数组进行线性扫描,复杂度为 $O(n m)$,计算结果复杂度为 $O(1)$。整体复杂度为 $O(n m)$
  • 空间复杂度:$O(n * m)$

二维前缀和模板【重点】

下面重点分享下前缀和模板该如何记忆,其实很多模板都可以按照类似方式进行记忆。

虽然「二维前缀和」的模板相比「一维前缀和」的模板要长,但是逻辑是清晰的,可以现场推导。

当然也可以在理解的基础上,使用以下方式进行记忆:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
// 预处理前缀和数组
{
sum = new int[n + 1][m + 1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 当前格子(和) = 上方的格子(和) + 左边的格子(和) - 左上角的格子(和) + 当前格子(值)【和是指对应的前缀和,值是指原数组中的值】
sum[i][j] = sum[i - 1][j] + sum[i][j - 1] - sum[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}

// 首先我们要令左上角为 (x1, y1) 右下角为 (x2, y2)
// 计算 (x1, y1, x2, y2) 的结果
{
// 前缀和是从 1 开始,原数组是从 0 开始,上来先将原数组坐标全部 +1,转换为前缀和坐标
x1++; y1++; x2++; y2++;
// 记作 22 - 12 - 21 + 11,然后 不减,减第一位,减第二位,减两位
// 也可以记作 22 - 12(x - 1) - 21(y - 1) + 11(x y 都 - 1)
ans = sum[x2][y2] - sum[x1 - 1][y2] - sum[x2][y1 - 1] + sum[x1 - 1][y1 - 1];
}

最后

这是我们「刷穿 LeetCode」系列文章的第 No.304 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。