题目描述
这是 LeetCode 上的 304. 二维区域和检索 - 矩阵不可变 ，难度为 中等。
Tag : 「前缀和」
给定一个二维矩阵，计算其子矩形范围内元素的总和，该子矩阵的左上角为 (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 复制代码
提示：
- 你可以假设矩阵不可变。
- 会多次调用 sumRegion 方法。
- 你可以假设 row1 ≤ row2 且 col1 ≤ col2 。
前缀和解法（二维）
真就是今天的「每日一题」呗 ~
这是一道「二维前缀和」的裸题。
「二维前缀和」解决的是二维矩阵中的矩形区域求和问题。
二维前缀和数组中的每一个格子记录的是「以当前位置为区域的右下角（区域左上角恒定为原数组的左上角）的区域和」
贴一张官解示意图，我觉得很清晰：
如果觉得不清晰，请将将 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)
代码：
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(n∗m)，计算结果复杂度为 O(1)O(1)。整体复杂度为 O(n * m)O(n∗m)
- 空间复杂度：O(n * m)O(n∗m)
二维前缀和模板【重点】
下面重点分享下前缀和模板该如何记忆，其实很多模板都可以按照类似方式进行记忆。
虽然「二维前缀和」的模板相比「一维前缀和」的模板要长，但是逻辑是清晰的，可以现场推导。
当然也可以在理解的基础上，使用以下方式进行记忆：
// 预处理前缀和数组 { 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 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour… 。
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
