Java算法
前缀和算法详解及 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