什么是前缀和？

前缀和是一种重要的预处理，能大大降低查问的工夫复杂度。咱们能够简略了解为“数列的前 n 项的和”。这个概念其实很容易了解，即一个数组中，第 n 位存储的是数组前 n 个数字的和。

通过一个例子来进行说明会更清晰。题目形容：有一个长度为 N 的整数数组 A，要求返回一个新的数组 B，其中 B 的第 i 个数 B[i]是原数组 A 前 i 项和。

这道题理论就是让你求数组 A 的前缀和。对 [1,2,3,4,5,6] 来说，其前缀和能够是 pre=[1,3,6,10,15,21]。咱们能够应用公式 pre[????]=pre[????−1]+nums[????]失去每一位前缀和的值，从而通过前缀和进行相应的计算和解题。其实前缀和的概念很简略，但艰难的是如何在题目中应用前缀和以及如何应用前缀和的关系来进行解题。理论的题目更多不是间接让你求前缀和，而是你须要本人应用前缀和来优化算法的某一个性能瓶颈。

而如果数组是负数的话，前缀和数组会是一个枯燥不递加序列，因而前缀和 + 二分也会是一个考点，不过这种题目难度个别是力扣的艰难难度。对于这个知识点，我会在之后的二分专题方做更多介绍。

简略的二维前缀和

下面提到的例子是一维数组的前缀和，简称一维前缀和。那么二维前缀和实际上就是二维数组上的前缀和了。一维数组的前缀和也是一个一维数组，同样地，二维数组的前缀和也是一个二维的数组。

比方对于如下的一个二维矩阵：

1 2 3 45 6 7 8

定义二维前缀和矩阵 $pres$，$pres{x,y} = \sum\limits_{i=1}^x \sum\limits_{j=1}^y a_{i,j}$。通过这样的解决，下面矩阵的二维前缀和就变成了：

1  3  6 106 14 24 36

那么如何用代码计算二维数组的前缀和呢？简略的二维前缀和的求解办法是基于容斥原理的。

比方咱们想求如图中灰色局部的和。

一种形式就是用下图中两个绿色局部的矩阵加起来（之所以用绿色局部相加是因为这两局部曾经通过下面预处理计算好了，能够在 $O(1)$ 的工夫失去），这样咱们就会多加一块区域，这块区域就是如图黄色局部，咱们再减去黄色局部就好了，最初再加上以后地位自身就行了。

比方咱们想要求 $sum_{i,j}$，则能够通过 $sum_{i - 1,j} + sum_{i,j - 1} - sum_{i - 1,j - 1} + a_{i,j}$ 的形式来实现。这样我就能够通过 $O(m * n)$ 的预处理计算二维前缀和矩阵（m 和 n 别离为矩阵的长和宽），再通过 $O(1)$ 的工夫计算出任意小矩阵的和。其底层原理就是下面提到的容斥原理，大家能够通过画图的形式来感受一下。

如何将二维前缀和转化为一维前缀和

然而实际上，咱们也可不构建一个前缀和数组，而是间接原地批改。

一维前缀和同样能够采纳这一技巧。

比方咱们能够先不思考行之间的关联，而是事后计算出每一行的前缀和。对于计算每一行的前缀和就是一维前缀和啦。接下来通过固定两个列的端点的形式计算每一行的区域和。代码上，咱们能够通过三层循环来实现， 其中两层循环用来固定列端点，另一层用于枚举所有行。

其实也能够反过来。即固定行的左右端点并枚举列，上面的题目会提到这一点。

代码示意：

# 事后构建行的前缀和for row in matrix:    for i in range(n - 1):        row[i + 1] += row[i]

比方矩阵：

1 2 3 45 6 7 8

则会变为：

1 3 6 105 11 18 26

接下来：

# 固定列的两个端点，即枚举所有列的组合for i in range(n):    for j in range(i, n):        pres = [0]        pre = 0        # 枚举所有行        for k in range(m):            # matrix[k] 其实曾经是上一步预处理的每一行的前缀和了。因而 matrix[k][j] - (matrix[k][i - 1] 就是每一行 [i, j] 的区域和。            pre += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)            pres.append(pre)

下面代码做的事件形象来看，就是先在程度方向计算前缀和，而后在竖直方向计算前缀和，而不是同时在两个方向计算。

如果把 [i, j] 的区域和看出是一个数的话，问题就和一维前缀和一样了。代码：

for i in range(n):    for j in range(i, n):        pres = [0]        pre = 0        # 枚举所有行        for k in range(m):            # 其中 a 为[i, j] 的区域和            pre += a            pres.append(pre)

题目举荐

有了下面的常识，咱们就能够来解决上面两道题。尽管上面两道题的难度都是 hard，不过总体难度并不高。这两道题之所以是 hard， 是因为其考查了不止一个知识点。这也是 hard 题目的一种类型，即同时考查多个知识点。

363. 矩形区域不超过 K 的最大数值和

题目地址

https://leetcode-cn.com/probl...

题目形容

给定一个非空二维矩阵 matrix 和一个整数 k，找到这个矩阵外部不大于 k 的最大矩形和。示例:输出: matrix = [[1,0,1],[0,-2,3]], k = 2输入: 2解释: 矩形区域 [[0, 1], [-2, 3]] 的数值和是 2，且 2 是不超过 k 的最大数字（k = 2）。阐明：矩阵内的矩形区域面积必须大于 0。如果行数远大于列数，你将如何解答呢？

前置常识

  • 二维前缀和
  • 二分法

思路

后面提到了因为非正数数组的二维前缀和是一个非递加的数组，因而经常和二分联合考查。实际上即便数组不是非负的，咱们依然有可能构建一个有序的前缀和，从而应用二分，这道题就是一个例子。

首先咱们能够用下面提到的技巧计算二维数组的前缀和，这样咱们就能够计算疾速地任意子矩阵的和了。留神到下面咱们计算的 pres 数组是一个一维数组，但矩阵其实可能为正数，因而不满足枯燥性。这里咱们能够手动保护 pres 枯燥递增，这样就能够应用二分法在 $logN$ 的工夫求出以以后项 i 结尾的不大于 k 的最大矩形和，那么答案就是所有的以任意索引 x 结尾的不大于 k 的最大矩形和的最大值。

之所以能够手动保护 pres 数组枯燥增也可失去正确后果的起因是题目只须要求子矩阵和，而不是求具体的子矩阵。

代码上，当计算出 pres 后，咱们其实须要寻找大于等于 pre - k 的最小数 x。这样矩阵和 pre - x 能力满足 pre - x <= k，应用最左插入二分模板即可解决。

关键点

  • 典型的二维前缀和 + 二分题目

代码

  • 语言反对：Python3

Python3 Code:

class Solution:    def maxSumSubmatrix(self, matrix: List[List[int]], K: int) -> int:        m, n = len(matrix), len(matrix[0])        ans = float("-inf")        for row in matrix:            for i in range(n - 1):                row[i + 1] += row[i]        for i in range(n):            for j in range(i, n):                pres = [0]                pre = 0                for k in range(m):                    pre += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)                    # 寻找大于等于 pre - k 的最小数，且这个数不能比 pre 大。比方 pre = 10， k = 3，就要找大于等于 7 的最小数，这个数不能大于 10。                    # 为了达到这个目标，能够应用 bisect_left 来实现。（应用 bisect_right 不蕴含等号）                    idx = bisect.bisect_left(pres, pre - K)                    # 如果 i == len(pre) 示意 pres 中的数都小于 pre - k，也就是说无解                    if idx < len(pres):                        # 由 bisect_left 性质可知 pre - pres[i] >= 0                        ans = max(ans, pre - pres[idx])                    idx = bisect.bisect_left(pres, pre)                    pres[idx:idx] = [pre]                    # 或者将下面两行代码替换为 bisect.insort(pres, pre)        return -1 if ans == float("-inf") else ans

复杂度剖析

令 n 为数组长度。

  • 工夫复杂度：$O(m * n ^ 2)$
  • 空间复杂度：$O(m)$

题目给了一个 follow up：如果行数远大于列数，你将如何解答呢？ 实际上，如果行数远大于列数，由复杂度剖析可知空间复杂度会很高。咱们能够将行列兑换，这样空间复杂度是 $O(n)$。换句话说，咱们能够通过行列的调换做到空间复杂度为 $O(min(m, n))$。

1074. 元素和为目标值的子矩阵数量

题目地址

https://leetcode-cn.com/probl...

题目形容

给出矩阵 matrix 和目标值 target，返回元素总和等于目标值的非空子矩阵的数量。子矩阵 x1, y1, x2, y2 是满足 x1 <= x <= x2 且 y1 <= y <= y2 的所有单元 matrix[x][y] 的汇合。如果 (x1, y1, x2, y2) 和 (x1', y1', x2', y2') 两个子矩阵中局部坐标不同（如：x1 != x1'），那么这两个子矩阵也不同。 示例 1：输出：matrix = [[0,1,0],[1,1,1],[0,1,0]], target = 0输入：4解释：四个只含 0 的 1x1 子矩阵。示例 2：输出：matrix = [[1,-1],[-1,1]], target = 0输入：5解释：两个 1x2 子矩阵，加上两个 2x1 子矩阵，再加上一个 2x2 子矩阵。 提醒：1 <= matrix.length <= 3001 <= matrix[0].length <= 300-1000 <= matrix[i] <= 1000-10^8 <= target <= 10^8

前置常识

  • 二维前缀和

思路

和下面题目相似。不过这道题是求子矩阵和刚好等于某个目标值的数目。

咱们无妨先对问题进行简化。比方题目要求的是一维数组中，子数组（间断）的和等于目标值 target 的数目。咱们该如何做？

这很容易，咱们只须要：

  • 边遍历边计算前缀和。
  • 比方以后的前缀和是 cur，那么咱们要找的前缀和 x 应该满足 cur - x = target，因为这样以后地位和 x 的之间的子数组和才是 target。即咱们须要找前缀和为 cur - target 的数目。 这提醒咱们应用哈希表记录每一种前缀和呈现的次数。

因为仅仅是求数目，不波及到求具体的子矩阵信息，因而应用相似下面的解法求出二维前缀和。接下来，应用和一维前缀和同样的办法即可求出答案。

关键点

  • 次要考查一维前缀和到二维前缀和的过渡是否把握

代码

  • 语言反对：Python3

Python3 Code:

class Solution:    def numSubmatrixSumTarget(self, matrix, target):        m, n = len(matrix), len(matrix[0])        for row in matrix:            for i in range(n - 1):                row[i + 1] += row[i]        ans = 0        for i in range(n):            for j in range(i, n):                c = collections.defaultdict(int)                cur, c[0] = 0, 1                for k in range(m):                    cur += matrix[k][j] - (matrix[k][i - 1] if i > 0 else 0)                    ans += c[cur - target]                    c[cur] += 1        return ans

复杂度剖析

  • 工夫复杂度：$O(m * n ^ 2)$
  • 空间复杂度：$O(m)$

和下面一样，咱们能够将行列对换，这样空间复杂度是 $O(n)$。换句话说，咱们能够通过行列的调换做到空间复杂度为 $O(min(m, n))$。

力扣的小伙伴能够关注我，这样就会第一工夫收到我的动静啦~

以上就是本文的全部内容了。大家对此有何认识，欢送给我留言，我有工夫都会一一查看答复。更多算法套路能够拜访我的 LeetCode 题解仓库：https://github.com/azl3979858... 。 目前曾经 40K star 啦。大家也能够关注我的公众号《力扣加加》带你啃下算法这块硬骨头。