前缀和->专门用于快速得出数组某一段连续区间的和O(1)
牛克.DP34【】前缀和
牛克的hasnext我一直开始的时候搞不明白
当发现同一类问题的时候，可以用同一类问题来解决。
while(in.hasnext）无关紧要，你要不要都可以
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int n = in.nextInt(); int q = in.nextInt(); int []arr=new int[n+1]; while(in.hasNext()){ //预处理一个前缀和数组 for(int i=1;i<=n;i++){ arr[i]=in.nextInt(); } long []dp=new long[n+1]; for(int i=1;i<=n;i++){ dp[i]=dp[i-1]+arr[i]; } while(q>0){ int l=in.nextInt(); int m=in.nextInt(); System.out.println(dp[m]-dp[l-1]); q--; } } } }
牛克.DP35二维前缀和
解法1.暴力解法->模拟
前缀和思想
1.预处理出来一个前缀和矩阵
2.使用前缀和矩阵
ij:表示从[1][1]到ij位置位置的这段区间前缀和
dp[i][j]=dp[i-1][j]+dp[i][j-1]+arr[i][j]-dp[i][j];
很难想，我认为是，反正我没有见过 
结果的返回:
注意此时减去的c，应该是dp[x1-1][x2]因为[x1][x2]他这个点属于D的范围了，因为dpxy包含那个初始位置[x1][y1]的值是包含在内部的,
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 int m= in.nextInt(); int n= in.nextInt(); int q= in.nextInt(); int[][]arr=new int[m+1][n+1]; for (int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ arr[i][j]=in.nextInt(); } } long [][]dp=new long[m+1][n+1]; for (int i=1;i<=m;i++){ for(int j=1;j<=n;j++){ dp[i][j]=dp[i-1][j]+dp[i][j-1]-dp[i-1][j-1]+arr[i][j]; } } while(q>0){ int x=in.nextInt(); int y=in.nextInt(); int z=in.nextInt(); int p=in.nextInt(); System.out.println(dp[z][p]-dp[z][y-1]-dp[x-1][p]+dp[x-1][y-1]); q--; } } }
力扣724.寻找数组的中心下标
不要死记模版
如果全是前缀和，那么我们每次枚举一个中心下标，就要左边加一块，右边加一块
这样也很麻烦，所以推荐优秀的方法
前缀和与后缀和
class Solution { public static int pivotIndex(int[] nums) { //dp前缀和,0到i，区间的所有元素和 int[] dp = new int[nums.length]; dp[0] =nums[0]; for (int i = 1; i < nums.length; i++) { dp[i] = dp[i - 1] + nums[i]; } //dp2后缀和数组，length到i的所有元素和 int[] dp2 = new int[nums.length]; dp2[nums.length - 1] =nums[nums.length-1]; for (int i = nums.length - 2; i >= 0; i--) { dp2[i] = dp2[i + 1] + nums[i]; } for (int i = 0; i < nums.length; i++) { //最后左右都会相等，所以最后无论你加不加这个i位置的数组都是可以的 if (dp[i] == dp2[i]) { return i; } } return -1; } }
方法2：与下一题的思想一致，都是dp[i]设定的含义是从0位置到i-1不包含它本身
public static int pivotIndex(int[] nums) { //dp前缀和,0到i，区间的所有元素和 int n=nums.length; int[] dp = new int[n]; for (int i = 1; i < nums.length; i++) { dp[i] = dp[i - 1]+ nums[i-1]; } //dp2后缀和数组，length到i的所有元素和 int[] dp2 = new int[n]; for (int i = n - 2; i >=0; i--) { dp2[i] = dp2[i + 1] + nums[i+1]; } for (int i = 0; i < n; i++) { //最后左右都会相等，所以最后无论你加不加这个i位置的数组都是可以的 if (dp[i] == dp2[i]) { return i; } } return -1; }
力扣238.除自身以外数组的乘积
这个前缀和的思想一致，但是有不一样的地方
f[i]他是不包括自身的前缀乘积，g[i]那就是不包括自身的后缀乘积
f[i]:表示0-i-1区间内所有元素的乘积(f[i-1]是0-i-2位置)
f[i]=f[i-1]*nums[i-1];
g[i]:表示i+1到length-1(g[i+1]表示I+2到length-1位置
g[i]=g[i+1]*nums[i+1];
class Solution { public static int[] productExceptSelf(int[] nums) { int []f=new int[nums.length]; int []g=new int[nums.length]; int []k=new int[nums.length]; f[0]=1; for(int i=1;i<nums.length;i++){ //从1到i位置的乘积 f[i]=f[i-1]*nums[i-1]; } g[nums.length-1]=1; for(int j=nums.length-2;j>=0;j--){ g[j]=g[j+1]*nums[j+1]; } for(int i=0;i<nums.length-1;i++){ k[i]=f[i]*g[i]; } return k; } }
