【寻找one piece的算法之路】前缀和（一）

💐个人主页：初晴~

📚相关专栏：寻找one piece的刷题之路

什么是前缀和？

主要是通过预先计算数组或矩阵的前缀和，来快速查询子数组或子矩阵的和。这种算法可以用空间换时间，提高查询效率。

概念

给定一个数组 A，前缀和数组 PP 定义为：

P[i]=A[0]+A[1]+⋯+A[i]P[i]=A[0]+A[1]+⋯+A[i]

即 P[i]P[i] 是从数组开头到位置 ii 所有元素的和

计算前缀和

初始化：前缀和数组的第一个元素等于原数组的第一个元素，即 P[0]=A[0]。
迭代计算：对于每一个 i>0，计算 P[i]=P[i−1]+A[i]P[i]=P[i−1]+A[i]。

查询区间和

一旦前缀和数组构建完成，查询区间和的操作变得非常简单。如果要查询数组 AA 中从索引 ll 到索引 rr 的区间和，可以使用以下公式：

sum(l,r)=P[r]−P[l−1]sum(l,r)=P[r]−P[l−1]

注意，这里的 l−1 必须是非负的，因此查询的左端点 l 至少为 1（对于从 0 开始索引的数组，l 至少为 0）。

时间复杂度

预处理时间复杂度：构建前缀和数组的时间复杂度为 O(n)，其中 n 是数组的长度。
查询时间复杂度：查询区间和的时间复杂度为 O(1)，因为只需要一次简单的计算。

一、⼀维前缀和

题目链接

题目描述：

题目分析：

先准备一个数组dp【】来存储前缀和，dp【i】表示【1，i】区间内所有元素的和。我们可以通过一次遍历就求出前缀和数组，通过dp【i】=dp【i-1】+arr【i】来递推。

之后就可以通过前缀和数组快速求出“某一段区间”内所有元素的和

比如我们要查询区间【l，r】时，区间内元素和就为：dp【r】-dp【l-r】；

代码实现：

public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n=in.nextInt(),q=in.nextInt();long[] arr=new long[n+1];for(int i=1;i<=n;i++){arr[i]=arr[i-1]+in.nextInt();}for(int i=0;i<q;i++){int l=in.nextInt();int r=in.nextInt();System.out.println(arr[r]-arr[l-1]);}}
}

二、二维前缀和

题目链接

题目描述：

题目分析：

问题的关键在于我们能否搞出一个数组nums【】【】，让nums【i】【j】代表重【0,0】到【i，j】区域内所有元素的和。这样就有机会在O（1）的时间复杂度下快速查询出任意区域的元素和。

我们可以通过下图的方法建立前缀和数组，目的是为了避免繁琐的边界判定。这样下标从1开始填写，我们就能放心地使用【i-1】【j-1】下标的位置了：

我们可以将【0,0】到【i，j】区域划分为以下几块位置：

nums【i】【j】=红+篮+粉+绿

1、绿色区域的值就是arr【i】【j】的值

2、红+篮区域的值事实上就是【0,0】到【i-1，j】区域内的元素和，即nums【i-1】【j】

3、红+粉区域的值事实上就是【0,0】到【i，j-1】区域内的元素和，即nums【i】【j-1】

4、而红色区域的值事实上就是【0,0】到【i-1，j-1】区域内的元素和，即nums【i-1】【j-1】

这样我们就可以得到整个区域的元素和，就等于红蓝+红粉-红+绿

也就可以得到 nums[i][j]=nums[i-1][j]+nums[i][j-1]-nums[i-1][j-1]+arr[i][j]

这样我们就可以通过一次遍历求出前缀和数组了。

求出前缀和数组后，我们还得想办法通过前缀和数组来查询计算出任意一块区域的元素和

类似的，我们可以划分出如下几个区域：

我们的目的就是求出绿色区域【x1，y1】到【x2，y2】区域内元素的和

由于我们已经求出前缀和了，于是我们可能得到一下区域的值：

1、红蓝粉绿整个区域的元素和为nums【x2，y2】

2、红蓝区域的元素和为 nums【x1-1】【y2】

3、红粉区域的元素和为 nums【x2】【y1-1】

4、红色区域的元素和为 nums【x1-1】【y1-1】

这样，我们就可以得到绿色区域值等于红蓝粉绿-红蓝-红粉+红

也就是 ans=nums[x2][y2]-nums[x2][y1-1]-nums[x1-1][y2]+nums[x1-1][y1-1]

代码实现：

public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in);int n=in.nextInt(),m=in.nextInt(),q=in.nextInt();int[][] arr=new int[n+1][m+1];long[][] nums=new long[n+1][m+1];for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){arr[i][j]=in.nextInt();}}for(int i=1;i<=n;i++){for(int j=1;j<=m;j++){nums[i][j]=nums[i-1][j]+nums[i][j-1]-nums[i-1][j-1]+arr[i][j];}}for(int i=0;i<q;i++){int x1=in.nextInt();int y1=in.nextInt();int x2=in.nextInt();int y2=in.nextInt();System.out.println(nums[x2][y2]-nums[x2][y1-1]-nums[x1-1][y2]+nums[x1-1][y1-1]);}}
}

三、寻找数组的中心下标

题目链接

题目描述：

题目分析：

从中⼼下标的定义可知，除中⼼下标的元素外，该元素左边的「前缀和」等于该元素右边的「后缀

和」。

事实上，我们并不需要遍历两次分别求出前缀和和后缀和，可以通过一些技巧优化一下。

通过两个变量 l 和 r，分别该坐标 i 前后的前缀和和后缀和。

先遍历一遍数组，让 r 记录下整个数组的元素和。
接着再进行一次遍历，让 r 减去当前遍历元素的值，这样，r 就能表示 i 坐标后的后缀和，
然后比较此时 l 和 r 的值，如果相等，就声明找到目标位置了，直接返回；如果不相等，则让 l 加上当前遍历元素的值，这样 l 也就能表示遍历途中的前缀和了
重复上述步骤，就能解决题目要求了

代码实现：

class Solution {public int pivotIndex(int[] nums) {int n=nums.length,l=0,r=0;for(int num:nums){r+=num;}for(int i=0;i<n;i++){r-=nums[i];if(l==r)return i;l+=nums[i];}return -1;}
}

四、除自身以外数组的乘积

题目链接

题目描述：

题目分析：

注意题⽬的要求，不能使⽤除法，并且要在 O(N) 的时间复杂度内完成该题。那么我们就不能使

⽤暴⼒的解法，以及求出整个数组的乘积，然后除以单个元素的⽅法。

继续分析，根据题意，对于每⼀个位置的最终结果 ret[i] ，它是由两部分组成的：

nums[0] * nums[1] * nums[2] * ... * nums[i - 1]
nums[i + 1] * nums[i + 2] * ... * nums[n - 1]

于是，我们可以利⽤前缀和的思想，使⽤两个数组 qian 和 hou，分别处理出来两个信息：

qian 表⽰：i 位置之前的所有元素，即 [0, i - 1] 区间内所有元素的前缀乘积，
hou 表⽰： i 位置之后的所有元素，即 [i + 1, n - 1] 区间内所有元素的后缀乘积

然后再处理最终结果。

代码实现：

class Solution {public int[] productExceptSelf(int[] nums) {int n=nums.length;int[] answer=new int[n];int[] qian=new int[n],hou=new int[n]; qian[0]=1;hou[n-1]=1;for(int i=1;i<n;i++){qian[i]=qian[i-1]*nums[i-1];}for(int i=n-2;i>=0;i--){hou[i]=hou[i+1]*nums[i+1];}for(int i=0;i<n;i++){answer[i]=qian[i]*hou[i];}return answer;}
}