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;}
}
