前缀和算法专题（1）
找往期文章包括但不限于本期文章中不懂的知识点：
个人主页：我要学编程(ಥ_ಥ)-CSDN博客
所属专栏： 优选算法专题
目录
前缀和算法的介绍
DP34【模板】前缀和
DP35【模板】二维前缀和
238. 除自身以外数组的乘积
前缀和算法的介绍
前缀和主要用于处理求一段子序列的和的问题，有点和我们前面学习的滑动窗口算法类似，只不过前缀和主要是关注于求和问题。
代码实现：
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. 寻找数组的中心下标
题目：
给你一个整数数组
nums，请计算数组的 中心下标 。数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为
0，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回
-1。示例 1：
输入：nums = [1, 7, 3, 6, 5, 6]输出：3解释：中心下标是 3 。左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ，右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。示例 2：
输入：nums = [1, 2, 3]输出：-1解释：数组中不存在满足此条件的中心下标。示例 3：
输入：nums = [2, 1, -1]输出：0解释：中心下标是 0 。左侧数之和 sum = 0 ，（下标 0 左侧不存在元素），右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。提示：
1 <= nums.length <= 104-1000 <= nums[i] <= 1000
思路： 题目就是让我们在一个数组中找到一个下标，其对应位置两边的和都是相等的（如果两边已经相等的话，那么这个值加不加都无所谓，加上去，两边还是相等，不加也是相等的）。题目还要求让我们求出最左边满足要求的，那么我们直接从最左边开始遍历即可。
代码实现：
暴力枚举：
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 = 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 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. 除自身以外数组的乘积
题目：
给你一个整数数组
nums，返回 数组answer，其中answer[i]等于nums中除nums[i]之外其余各元素的乘积 。题目数据 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。请 不要使用除法，且在
O(n)时间复杂度内完成此题。示例 1:
输入: nums = [1,2,3,4]输出: [24,12,8,6]示例 2:
输入: nums = [-1,1,0,-3,3]输出: [0,0,9,0,0]提示：
2 <= nums.length <= 105-30 <= nums[i] <= 30- 保证 数组
nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
思路：读完题目，应该是很快能够想到暴力枚举的思路的。直接外层循环遍历填充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 = 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）的学习之旅就到此结束啦！我们下一期再一起学习吧！
