前缀和算法详解及 LeetCode 经典题目解析
本文详细讲解了前缀和算法及其在 LeetCode 经典题目中的应用。内容涵盖了一维前缀和、前缀积、以及结合哈希表解决子数组求和问题,并扩展到二维前缀和处理矩阵区域和。文章通过寻找数组中心下标、除自身以外数组的乘积、和为 K 的子数组、和可被 K 整除的子数组、连续数组及矩阵区域和六个具体案例,对比了暴力解法与前缀和优化解法,重点分析了初始化、边界处理及时间复杂度优化策略,提供了完整的 Java 代码实现。

本文详细讲解了前缀和算法及其在 LeetCode 经典题目中的应用。内容涵盖了一维前缀和、前缀积、以及结合哈希表解决子数组求和问题,并扩展到二维前缀和处理矩阵区域和。文章通过寻找数组中心下标、除自身以外数组的乘积、和为 K 的子数组、和可被 K 整除的子数组、连续数组及矩阵区域和六个具体案例,对比了暴力解法与前缀和优化解法,重点分析了初始化、边界处理及时间复杂度优化策略,提供了完整的 Java 代码实现。

注意:前缀和表示以 nums[0] 为起始位置,一直到遍历位置所有元素组成的数组之和。

在遍历到一个元素时,判断这个元素左右的元素之和是否相等即可。每次遍历到一个元素,就要左边枚举一遍,右边枚举一遍;枚举一个元素的左右之和,时间复杂度为 O(N),所以暴力解法 O(N^2)。
我们在求 [0, i - 1] 和 [i+1 , n - 1] 区间的元素之和,就是在求一段连续区间的和,这就可以利用前缀和的预处理。
预处理前缀和数组和后缀和数组
因为本题需要求前面区间的和与后面区间的和,所以我们可以调整一下前缀和数组的表达方式。
我们用 f 表示前缀和数组,g 表示后缀和数组:

f[i] 表示 [0, i-1] 区间的元素之和,而前面的 dp[i] 表示的是 [1, i] 区间的元素之和,这题这样微调,是因为数组从 0 下标开始,且前缀和数组的元素 f[i],是不包括 arr[i] 元素的求和值; g[i] 表示 [i+1, n-1] 区间所有元素之和,之前是求 [i, n] 区间的和,微调的原理同上;
递推公式:

使用前缀和数组和后缀和数组
我们可以在 [0, n - 1] 区间,直接枚举预处理好的前缀和与后缀和数组,并且判断当前枚举的预处理数组元素 f[i], g[i] 是否相等,相等返回最左边的中心下标,否则返回 -1。

处理细节问题
代码实现:
public int pivotIndex(int[] nums) {
int n = nums.length;
if (n == 0) return -1;
int[] f = new int[n]; // 前缀和
int[] g = new int[n]; // 后缀和
// 初始化边界
f[0] = 0;
g[n - 1] = 0;
// 填充前缀和 f[i] = f[i-1] + nums[i-1]
for (int i = 1; i < n; i++) {
f[i] = f[i - 1] + nums[i - 1];
}
// 填充后缀和 g[i] = g[i+1] + nums[i+1]
for (int i = n - 2; i >= 0; i--) {
g[i] = g[i + 1] + nums[i + 1];
}
// 查找中心下标
for (int i = 0; i < n; i++) {
if (f[i] == g[i]) {
return i;
}
}
return -1;
}

每遍历到一个数组元素,就计算一次这个数组中,除该元素外的所有元素的乘积,得到的结果返回对应下标的 answer 中;时间复杂度 O(N^2)。
我们可以先看 nums 数组其中一个位置 nums[i]:
在计算 nums[i] 时=前,我们可以预处理前缀积数组&后缀积数组;当计算 nums[i] 时,我们就直接从预处理的数组拿值,就可以把计算 answer[i] 的时间复杂度降到 O(N)。
定义前缀积数组&后缀积数组:

解析 f[i] & g[i]


前缀和方法是典型的以空间换时间,预处理操作虽然多创建了一个数组,但是时间复杂度会得到质的提升。
使用前缀积数组&后缀积数组
创建一个与 nums 数组同等规模的数组 answer:
而在填 answer 时,只需要计算 answer[i] = f[i-1] * g[i+1]。
处理细节问题
处理填 g[i] 时需要从后往前填外,还需要注意初始化问题:

代码实现:
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] answer = new int[n];
int[] f = new int[n]; // 前缀积
int[] g = new int[n]; // 后缀积
// 初始化
f[0] = 1;
g[n - 1] = 1;
// 计算前缀积
for (int i = 1; i < n; i++) {
f[i] = f[i - 1] * nums[i - 1];
}
// 计算后缀积
for (int i = n - 2; i >= 0; i--) {
g[i] = g[i + 1] * nums[i + 1];
}
// 计算结果
for (int i = 0; i < n; i++) {
answer[i] = f[i] * g[i];
}
return answer;
}

我们可以使用 O(N^2) 的时间复杂度枚举出所有子数组。当我们向后枚举到一个元素,使得和为 k 时,不能停止,也就需要向后继续枚举。直到枚举完最后一个元素,此时起始下标的枚举才完成。所以这道题是不能用双指针(滑动窗口)来做优化的,因为这道题的不具备单调性,每一个元素可正可负可为 0。
引入一个概念:以 i 位置为结尾的所有子数组。这个概念和暴力枚举相呼应,都是固定某一个位置,来枚举对应的情况。
因此,我们引入前缀和:
当枚举 i 位置时,其实我们已经知道以 i 位置为结尾的前缀和数组对应 i 位置的元素 sum[i] 是多少了。
所以,我们只需要找到一段区间的前缀和,让这个区间的前缀和等于 sum[i] - k 即可。
所以问题就转化成:在 [0, i-1] 区间内,有多少个前缀和为 sum[i] - k 的子数组。
但是,我们不能直接创建一个前缀和数组 sum,然后直接在 sum 中找前缀和为 sum[i] - k 的子数组,这样的做复杂度不如暴力解法。而哈希表用于快速查找某一个数,因此我们可以把前缀和塞入哈希表,然后把前缀和元素的出现个数,也放入哈希表中。
处理细节问题
代码实现:
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); // 初始化,处理从开头开始的子数组
int count = 0;
int sum = 0;
for (int num : nums) {
sum += num;
if (map.containsKey(sum - k)) {
count += map.get(sum - k);
}
map.put(sum, map.getOrDefault(sum, 0) + 1);
}
return count;
}

暴力枚举出所有子数组,把所有子数组的和相加,再判断这些和中能被 k 整除的子数组。这道题的元素也就是可以<=0,不存在单调性,因此也不能使用滑动窗口解题。
a % p (a < 0, p > 0) 结果为负数,修正方法为 (a % p + p) % p。对于下面的绿色部分,就是我们要找的,在 [0, i - 1] 区域中的一个符合要求的子数组,而符合要求的子数组,要满足元素之和 % k = 0。
通过对绿色部分子数组的表达式的进行进一步的转换,我们发现了下面这个条件:
而 sum % k = x % k,也可以反过来推出绿色部分元素之和 % k = 0。
所以,问题就转换成:求在 [0, i - 1] 区间内,找到有多少给前缀和 x 通过与 k 取余,x%k=sum%k,进而就能反推出绿色部分的子数组。
处理细节问题 为了保证蓝线部分两边的取模结果都为正数,需要对结果进行修正,并且正负统一。 所以问题最终转换成:在 [0, i - 1] 区间内,找到前缀和被 k 取模后(也就是前缀和除以 k 后,得到的余数结果),余数结果等于 (sum % k + k) % k 的所有子数组。 我们不需要真的去创建前缀和数组,而是定义一个变量,这个变量也不是用来存前缀和,而是存前缀和除以 k 后,得到的余数,并且在哈希表中的 key 也表示这个余数。 并且,把余数加入到哈希表中的时机,也是在遍历一个元素,就插入一次。
总结

代码实现:
public int subarraysDivByK(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, 1); // 初始化
int count = 0;
int sum = 0;
for (int num : nums) {
sum += num;
int remainder = (sum % k + k) % k; // 修正负数取模
if (map.containsKey(remainder)) {
count += map.get(remainder);
}
map.put(remainder, map.getOrDefault(remainder, 0) + 1);
}
return count;
}

如果要统计 0 和 1 的个数,来求出相同数量的最长连续子数组,那么这道题还是有一定难度的。 但是,如果我们把 0 转换成 -1,就变成找出一段连续和为 0 的最长子数组,难度会降低很多。
处理细节问题
代码实现:
public int findMaxLength(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
map.put(0, -1); // 初始化,key 为前缀和,val 为索引
int maxLen = 0;
int sum = 0;
for (int i = 0; i < nums.length; i++) {
sum += (nums[i] == 0 ? -1 : 1);
if (map.containsKey(sum)) {
maxLen = Math.max(maxLen, i - map.get(sum));
} else {
map.put(sum, i);
}
}
return maxLen;
}
我们演示示例一求 answer 矩阵的一个元素 answer[0][0]:
并且,如果扩展的矩阵超出原始边界,超出的元素格子都不考虑:

预处理前缀和数组
回顾快速求出二维前缀和递推公式:

处理细节问题

多加一行一列之和,我们是先根据 mat 来填 dp 表,再通过 dp 表填 answer,所以,在给 dp 表加上一行一列后,就会出现 mat 和 dp 的下标映射关系问题:
我们在求 dp[i][j] 时,在调整后,就变成找 mat[i-1][j-1] 对应的矩阵和,因此,我们的递推公式也会发送改变:
在通过 mat 填写好 dp 表之后,我们需要通过 dp 表来填写 answer,所以 dp 与 answer 的下标映射关系为 dp[i][j] 对应 answer[i-1][j-1]。使用前缀和数组

代码实现:
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length;
int n = mat[0].length;
int[][] dp = new int[m + 1][n + 1];
// 构建二维前缀和
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + mat[i - 1][j - 1];
}
}
int[][] ans = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int r1 = Math.max(0, i - k);
int c1 = Math.max(0, j - k);
int r2 = Math.min(m - 1, i + k);
int c2 = Math.min(n - 1, j + k);
// 利用前缀和计算矩形区域和
ans[i][j] = dp[r2 + 1][c2 + 1] - dp[r1][c2 + 1] - dp[r2 + 1][c1] + dp[r1][c1];
}
}
return ans;
}


微信公众号「极客日志」,在微信中扫描左侧二维码关注。展示文案:极客日志 zeeklog
暂无推荐文章,稍后可再来查看。
使用加密算法(如AES、TripleDES、Rabbit或RC4)加密和解密文本明文。 在线工具,加密/解密文本在线工具,online
查找任何按下的键的javascript键代码、代码、位置和修饰符。 在线工具,Keycode 信息在线工具,online
JavaScript 字符串转义/反转义;Java 风格 \uXXXX(Native2Ascii)编码与解码。 在线工具,Escape 与 Native 编解码在线工具,online
使用 Prettier 在浏览器内格式化 JavaScript 或 HTML 片段。 在线工具,JavaScript / HTML 格式化在线工具,online
Terser 压缩、变量名混淆,或 javascript-obfuscator 高强度混淆(体积会增大)。 在线工具,JavaScript 压缩与混淆在线工具,online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具,Base64 字符串编码/解码在线工具,online