基础算法（4）——前缀和
1. 前缀和
题目描述：
解法一：暴力解法
直接模拟实现题目流程即可
时间复杂度为，根据题目给出的条件
，肯定会超时
解法二：前缀和（适用题型：快速 求出数组中某一个 连续区间 的 和）
时间复杂度：
算法思路：
细节问题：为什么数组下标从 1 开始
当数组下标从 0 开始，dp[l - 1] 就成了 dp[-1] 造成数组越界异常
因此数组下标从 1 开始，若是数组下标从 0 开始时，需要处理边界情况
代码实现：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//1.读入数据
int n = in.nextInt();
int q = in.nextInt();
int[] arr = new int[n + 1];
for (int i = 1; i < n + 1; i++) {
arr[i] = in.nextInt();
}
//2.预处理一个前缀和数组
long[] dp = new long[n + 1]; //防溢出
dp[1] = arr[1];
for (int j = 2; j < n + 1; j++) {
dp[j] += dp[j - 1] + arr[j];
}
//3.使用前缀和数组
while (q > 0) {
int l = in.nextInt();
int r = in.nextInt();
System.out.println(dp[r] - dp[l - 1]);
q--;
}
}
}2. 二维前缀和
题目描述：
解法一：暴力解法（模拟）
时间复杂度：，会超时
解法二：前缀和
时间复杂度：
算法思路：
代码实现：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
//1.读入数据
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
int[][] arr = new int[n + 1][m + 1];
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
arr[i][j]= in.nextInt();
}
}
//2.预处理一个前缀和矩阵
long[][] dp = new long[n + 1][m + 1];
for (int i = 1; i < n + 1; i++) {
for (int j = 1; j < m + 1; j++) {
dp[i][j] = dp[i - 1][j] + dp[i][j - 1] + arr[i][j] - dp[i - 1][j - 1];
}
}
//3.使用前缀和矩阵
while (q > 0) {
int x1 = in.nextInt();
int y1 = in.nextInt();
int x2 = in.nextInt();
int y2 = in.nextInt();
System.out.println(dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1]);
q--;
}
}
}3. 寻找数组的中心下标
题目描述：
解法：前缀和
算法思路：
从中心下标的定义可知，除中心下标的元素外，该元素左边的【前缀和】等于该元素右边的【后缀和】
因此我们可以先预处理出来两个数组，一个表示前缀和，一个表示后缀和
然后用一个 for 循环枚举可能的中心下标，判断每一个位置的【前缀和】以及【后缀和】，如果二者相等，就返回当前下标
代码实现：
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
//f[i] 表示：[0, i - 1] 区间所有元素的和
//g[i] 表示：[i + 1, n - 1] 区间所有元素的和
int[] f = new int[n]; //前缀和数组
int[] g = new int[n]; //后缀和数组
//预处理前缀和后缀和数组（优化前）
//这里当i等于0时，f[0]本来就是0，没必要多加判断，直接从1位置开始遍历即可
// for (int i = 0; i < n; i++) {
// if (i == 0) {
// f[i] = 0;
// } else {
// f[i] = f[i - 1] + nums[i - 1];
// }
// }
//当i等于n-1时本来就是0，无需处理，直接从n-2处开始遍历即可
// for (int i = n - 1; i >= 0; i--) {
// if (i == n - 1) {
// g[i] = 0;
// } else {
// g[i] = g[i + 1] + nums[i + 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++) {
if (f[i] == g[i]) {
return i;
}
}
return -1;
}
}4. 除自身以外数组的乘积
题目描述：
解法：前缀积
算法思路：
根据题意，对于每一个位置的最终结果 answer[i] 都由两部分组成：
第一部分：nums[0] * nums[1] * nums[2] * ... * nums[i - 1]
第二部分：nums[i + 1] * nums[i + 2] * ... * nums[n - 1]
可以利用前缀和的思想，使用两个数组 f 和 g 分别处理出来两个信息：
代码实现：
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
//f[i] 表示[0, i-1] 区间内所有元素的乘积
//g[i] 表示[i+1, n-1] 区间内所有元素的乘积
int[] f = new int[n];
int[] g = new int[n];
int[] answer = new int[n];
//细节问题，这两个下标处的值需设为1，设为0的话任何数乘0都得0了
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;
}
}5. 和为 K 的子数组
题目描述：
解法一：暴力枚举
时间复杂度：
算法思路：
解法二：前缀和
算法思路：
代码实现：
class Solution {
public int subarraySum(int[] nums, int k) {
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
hash.put(0, 1); //对应整个数组元素和为 k 的情况
int sum = 0; //记录上一个位置的元素和
int ret = 0; //记录前缀和为 sum - k 出现的次数
for (int x : nums) {
sum += x; //计算当前位置的前缀和
ret += hash.getOrDefault(sum - k, 0); //统计结果
hash.put(sum, hash.getOrDefault(sum, 0) + 1); //把当前的前缀和放入哈希表
}
return ret;
}
}6. 和可被 K 整除的子数组
题目描述：
知识补充：
算法思路：
代码实现：
class Solution {
public int subarraysDivByK(int[] nums, int k) {
Map<Integer, Integer> hash = new HashMap<Integer, Integer>();
hash.put(0 % k, 1);
int sum = 0; //标记前一个位置的前缀和
int ret = 0; //表示最终结果
for (int x : nums) {
sum += x; //计算当前位置的前缀和
int r = (sum % k + k) % k;
ret += hash.getOrDefault(r, 0); //统计结果
hash.put(r, hash.getOrDefault(r, 0) + 1);
}
return ret;
}
}7. 连续数组
题目描述：
解法：前缀和 + 哈希表
代码实现：
class Solution {
public int findMaxLength(int[] nums) {
Map<Integer, Integer> hash = new HashMap<>();
hash.put(0, -1); //默认存在一个前缀和为 0 的情况
int sum = 0;
int ret = 0;
for (int i = 0; i < nums.length; i++) { //此处要求下标，所以不能用 foreach
//计算当前位置前缀和
//无需修改原数组，仅需判断当前位置为 0 时，加上 -1 即可
sum += (nums[i] == 0 ? -1 : 1);
if (hash.containsKey(sum)) { //判断哈希表中是否存在前缀和
ret = Math.max(ret, i - hash.get(sum));
} else { //若哈希表中不存在前缀和，则更新
hash.put(sum, i);
}
}
return ret;
}
}
实例：
8. 矩阵区域和
题目描述：
题目解析：
解法：二维前缀和
二维前缀和递推公式推导：
使用前缀和
算法思路：
此处将 answer 简写为 ans
第一步：当我们要求 ans[i][j] 时，仅需知道其对应的 x1、y1、x2、y2
第二步：下标的映射关系
代码实现：
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length;
int n = mat[0].length;
//1.预处理前缀和矩阵
int[][] dp = new int[m + 1][n + 1]; //此处 +1 操作就是为 dp 表增加一行一列
for (int i = 1; i <= m; i++) { //dp 表从(1,1)开始
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];
}
}
//2.使用
int[][] ret = new int[m][n];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
int x1 = Math.max(0, i - k) + 1;
int y1 = Math.max(0, j - k) + 1;
int x2 = Math.min(m - 1, i + k) + 1;
int y2 = Math.min(n - 1, j + k) + 1;
ret[i][j] = dp[x2][y2] - dp[x1 - 1][y2] - dp[x2][y1 - 1] + dp[x1 - 1][y1 - 1];
}
}
return ret;
}
}原文地址：https://blog.csdn.net/Yuan_o_/article/details/142265708
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！