算法_前缀和

DP34 【模板】前缀和

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(),q = in.nextInt();int[] arr = new int[n+1];for(int i = 1; i < n+1; i++){arr[i] = in.nextInt();}long[] dp = new long[n+1];for(int i = 1; i < n+1; i++){dp[i] = dp[i-1] + arr[i];}while(q > 0){int l = in.nextInt(), r = in.nextInt();System.out.println(dp[r] - dp[l-1]);q--;}// while (in.hasNextInt()) { // 注意 while 处理多个 case//     int a = in.nextInt();//     int b = in.nextInt();//     System.out.println(a + b);// }}
}

 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(), m = in.nextInt(), 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(); }}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][j-1] + dp[i-1][j] + arr[i][j] - dp[i-1][j-1];}}while(q > 0){int x1 = in.nextInt(),y1 = in.nextInt(),x2 = in.nextInt(),y2 = in.nextInt();System.out.println(dp[x2][y2]-dp[x1-1][y2]- dp[x2][y1-1] + dp[x1-1][y1-1]);q--;}// 注意 hasNext 和 hasNextLine 的区别}
}

 724. 寻找数组的中心下标

class Solution {public int pivotIndex(int[] nums) {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];}if(0 == dp[nums.length-1] -dp[0] ){return 0;}for(int i = 1; i < nums.length; i++){if(dp[i-1] == dp[nums.length-1] - dp[i]){return i;}}return -1;}
}

 238. 除自身以外数组的乘积

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

 560. 和为 K 的子数组

974. 和可被 K 整除的子数组