找往期文章包括但不限于本期文章中不懂的知识点：
目录
前缀和算法的介绍
前缀和主要用于处理求一段子序列的和的问题，有点和我们前面学习的滑动窗口算法类似，只不过前缀和主要是关注于求和问题。
代码实现：
public void prefix_sum(int[] array) {
int n = array.length;
int[] virtual_array = new int[n+1]; // 多申请一个方便计算
for (int i = 0; i < array.length; i++) {
virtual_array[i+1] = virtual_array[i] + array[i];
}
}DP34【模板】前缀和
题目：
思路：看到这种模拟的题目，我们首先想到的是暴力枚举去解决。
代码实现：
暴力枚举：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
int[] array = new int[n]; // 原始数组
int i = 0;
for (int x : array) { // 初始化原始数组
array[i++] = in.nextInt();
}
int[][] array_L_R = new int[q][2]; // 查询数组
i = 0;
for (int[] x : array_L_R) { // 初始化查询数组
x[0] = in.nextInt();
x[1] = in.nextInt();
}
for (i = 0; i < q; i++) {
int[] arr = array_L_R[i]; // 再一次细化查询数组
int left = arr[0];
int right = arr[1];
long sum = 0; // 注意题目给的数据范围
for (int j = left-1; j < right; j++) {
sum += array[j];
}
System.out.println(sum);
}
}
}上面这种简单的暴力模拟，在面对数据量很大时，肯定是行不通的。题目是让我们查找子数组的和，即前缀和的题目。
代码实现：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int q = in.nextInt();
int[] array = new int[n]; // 原始数组
int i = 0;
for (int x : array) { // 初始化原始数组
array[i++] = in.nextInt();
}
// 由于辅助数组是记录前缀和，因此数据也得用long来保存
long[] virtual_array = new long[n+1]; // 辅助数组，记录前缀和
for (i = 0; i < n; i++) { // 初始化辅助数组
virtual_array[i+1] = virtual_array[i] + array[i];
}
int[][] array_L_R = new int[q][2]; // 查询数组
i = 0;
for (int[] x : array_L_R) { // 初始化查询数组
x[0] = in.nextInt();
x[1] = in.nextInt();
}
for (i = 0; i < q; i++) {
int[] arr = array_L_R[i]; // 再一次细化查询数组
int left = arr[0];
int right = arr[1];
long sum = virtual_array[right] - virtual_array[left-1];
System.out.println(sum);
}
}
}DP35【模板】二维前缀和
题目：
思路： 和上一题一样，首先，还是想到暴力枚举的思路去模拟实现。
代码实现：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
// 处理输入
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
int[][] array = new int[n][m];
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
array[i][j] = in.nextInt();
}
}
int[][] query = new int[q][4];
for (int i = 0; i < q; i++) {
for (int j = 0; j < 4; j++) {
query[i][j] = in.nextInt();
}
}
// 处理查询
for (int i = 0; i < q; i++) {
// 定位
int a1 = query[i][0];
int b1 = query[i][1];
int a2 = query[i][2];
int b2 = query[i][3];
long sum = 0; // 注意数据范围
for (int j = a1-1; j < a2; j++) {
for (int k = b1-1; k < b2; k++) {
sum += array[j][k];
}
}
System.out.println(sum);
}
}
}上面的代码最终会运行超时，时间复杂度为O(m * n * q)。最坏情况，遍历整个数组 q次。
因此，我们得优化上面的代码，题目是让我们求一段连续序列的和，因此我们可以采用前缀和的方法，来求出数组对应位置的前缀和。
下面是求二维数组前缀和的方法以及推导过程。
笨方法的代码实现：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
// 处理输入
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
int[][] array = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
array[i][j] = in.nextInt();
}
}
int[][] query = new int[q][4];
for (int i = 0; i < q; i++) {
for (int j = 0; j < 4; j++) {
query[i][j] = in.nextInt();
}
}
// 创建辅助数组
long[][] virtual_array = new long[n+1][m+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
// 只计算一维数组的和（上一题推导出来的公式）
virtual_array[i][j] = virtual_array[i][j-1] + array[i][j];
}
}
// 处理查询
for (int i = 0; i < q; i++) {
// 定位
int a1 = query[i][0];
int b1 = query[i][1];
int a2 = query[i][2];
int b2 = query[i][3];
long sum = 0; // 注意数据范围
for (int j = a1; j <= a2; j++) {
// （一维数组）列的和，只需要加上最后一列即可
sum += (virtual_array[j][b2] - virtual_array[j][b1-1]);
}
System.out.println(sum);
}
}
}找规律方法代码实现：
import java.util.Scanner;
// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
public static void main(String[] args) {
// 处理输入
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int m = in.nextInt();
int q = in.nextInt();
int[][] array = new int[n+1][m+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
array[i][j] = in.nextInt();
}
}
int[][] query = new int[q][4];
for (int i = 0; i < q; i++) {
for (int j = 0; j < 4; j++) {
query[i][j] = in.nextInt();
}
}
// 创建辅助数组
long[][] virtual_array = new long[n+1][m+1];
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
virtual_array[i][j] = virtual_array[i][j-1] + virtual_array[i-1][j] + array[i][j] - virtual_array[i-1][j-1];
}
}
// 处理查询
for (int i = 0; i < q; i++) {
// 定位
int a1 = query[i][0];
int b1 = query[i][1];
int a2 = query[i][2];
int b2 = query[i][3];
long sum = 0; // 注意数据范围
sum = virtual_array[a2][b2] - virtual_array[a1-1][b2] - virtual_array[a2][b1-1] + virtual_array[a1-1][b1-1];
System.out.println(sum);
}
}
}只要我们将规律推导出来后，代码的实现还是比较简单的（重在找出规律）。
不管是笨方法，还是找规律的方法，只要把题目做出来了，就是好的方法。
724. 寻找数组的中心下标
题目：
思路： 题目就是让我们在一个数组中找到一个下标，其对应位置两边的和都是相等的（如果两边已经相等的话，那么这个值加不加都无所谓，加上去，两边还是相等，不加也是相等的）。题目还要求让我们求出最左边满足要求的，那么我们直接从最左边开始遍历即可。
代码实现：
暴力枚举：
class Solution {
public int pivotIndex2(int[] nums) {
// 暴力枚举
for (int i = 0; i < nums.length; i++) { // 确定中心下标
// 计算出右侧的值
int right_sum = 0;
for (int j = i+1; j < nums.length; j++) {
right_sum += nums[j];
}
// 计算出左侧的值
int left_sum = 0;
for (int k = i-1; k >= 0; k--) {
left_sum += nums[k];
}
// 比较两个值
if (left_sum == right_sum) {
return i;
}
}
return -1;
}
}这个暴力枚举的思路还是很容易想到的，但是其时间复杂度过大（O(N^2)），不过这个还是可以通过全部的测试用例。这个暴力枚举的时间，主要是浪费在求 i 下标两侧的和上面，因此我们也是要想办法优化这个求和方式。 我们可以创建两个辅助数组，在一开始就将 [0，i] 位置的和求出来，这样就避免了大量的重复计算。
代码实现：
class Solution {
public int pivotIndex(int[] nums) {
// 前缀和优化
// 创建两个辅助数组
int n = nums.length;
int[] right_nums = new int[n+2]; // 为了更好的计算
int[] left_nums = new int[n+1];
for (int i = 1; i < n+1; i++) {
left_nums[i] = left_nums[i-1] + nums[i-1];
}
for (int i = n; i > 0; i--) {
right_nums[i] = right_nums[i+1] + nums[i-1];
}
for (int i = 0; i < nums.length; i++) { // 确定中心下标
// 计算出右侧的值
int right_sum = right_nums[i+2];
// 计算出左侧的值
int left_sum = left_nums[i];
// 比较两个值
if (left_sum == right_sum) {
return i;
}
}
return -1;
}
}注意：上面暴力枚举的方法，没有加上 i 位置对应的值，而利用前缀和思想优化后的代码是加上了 i 位置对应的值，但我们知道这个不影响最终的比较结果。
经过上面两道题目的洗礼，这一题还是挺简单的（毕竟暴力枚举都能写出来）。
238. 除自身以外数组的乘积
题目：
思路：读完题目，应该是很快能够想到暴力枚举的思路的。直接外层循环遍历填充ans数组，内层循环遍历求题目要求的值。
代码实现：
class Solution {
public int[] productExceptSelf(int[] nums) {
// 暴力枚举
int len = nums.length;
int[] ans = new int[len];
for (int i = 0; i < len; i++) {
// 计算出i位置之外，其余元素的乘积
int n = 1; // 这里一定不能是0
for (int j = 0; j < len; j++) {
if (j == i) { // 排除自身
continue;
}
if (nums[j] == 0) { // 存在0的话，那么最终的结果一定是0
n = 0;
break;
}
n *= nums[j];
}
ans[i] = n;
}
return ans;
}
}这一题和上一题不同，这里的暴力枚举的代码不能够通过全部的测试用例。因此，我们得想办法来优化暴力枚举的代码。暴力枚举的代码主要是在给 ans数组填充值的时候，计算的方法过于暴力，因此我们得优化这里。
优化方法：直接遍历数组将数组的积全部求出来，再去遍历数组，除以当前位置的的值即可。
代码实现：
class Solution {
public int[] productExceptSelf1(int[] nums) {
int len = nums.length;
int[] ans = new int[len];
int n = 1; // 这里一定不能是0
// 先将全部的值计算出来
for (int i = 0; i < len; i++) {
if (nums[i] == 0) { // 数组中出现0元素，就无需计算了
n = 0;
break;
}
n *= nums[i];
}
Arrays.fill(ans, 1); // 一定要填充为1，之后才能使用
for (int i = 0; i < len; i++) {
// 计算出i位置之外，其余元素的乘积
if (n == 0) { // 说明数组中存在0元素
// 判断当前元素是不是0
if (nums[i] == 0) {
// 计算除其之外的乘积
for (int j = 0; j < len; j++) {
if (j == i) { // 排除自身
continue;
}
ans[i] *= nums[j]; // 先得将ans中的元素全部初始化为1
}
} else {
ans[i] = 0;
}
} else { // 直接除以当前位置即可
ans[i] = n / nums[i];
}
}
return ans;
}
}注意：这个方法在笔试的时候，是可以去捡漏的，但是在面试中最好不要使用。因为用这个方法直接将题目降低了一个档次，会影响到面试官对我们的评价（面试官心里：不怎么懂算法啊）。
既然不能提前把数组的积计算出来，然后再去除以当前位置的值，那么只能另辟蹊径了。
其实求数组中除自身之外其余数组值的乘积， 这个条件可以将数组分成三部分：0~i-1，i，i+1~n-1 ---> [0，i-1]的乘积 * [i+1，n-1]的乘积 ---> 这个符合我们要求的。这也刚好符合前缀和的思想。
下图有详细说明：
因此，我们可以采用 前缀和的思想来写。
代码实现：
class Solution {
public int[] productExceptSelf(int[] nums) {
// 前缀和思想优化
int n = nums.length;
int[] ans = new int[n];
int[] left_nums = new int[n+1];
int[] right_nums = new int[n+1];
// 初始化数组（下面两种方式都可以）
// Arrays.fill(left_nums, 1);
// Arrays.fill(right_nums, 1);
left_nums[0] = 1;
right_nums[n-1] = 1;
// 填充数组(0和n-1对应的数组得特殊处理)
for (int i = 1; i <= n; i++) {
left_nums[i] = left_nums[i-1] * nums[i-1];
}
for (int i = n-2; i >= 0; i--) {
right_nums[i] = right_nums[i+1] * nums[i+1];
}
// 开始填充ans数组
for (int i = 0; i < n; i++) {
ans[i] = left_nums[i] * right_nums[i];
}
return ans;
}
}注意：这里前缀积和后缀积的数组的空间大小可以是n。
好啦！本期 前缀和算法专题（1）的学习之旅就到此结束啦！我们下一期再一起学习吧！