目录
一维数组前缀和
二维数组前缀和
寻找数组的中心下标
除了自身以外数组的乘积
一维数组前缀和
一维数组前缀和
public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { // 注意 while 处理多个 case int n = in.nextInt() , q = in.nextInt(); int[] arr = new int[n + 1]; 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 left = in.nextInt() , right = in.nextInt(); System.out.println(dp[right] - dp[left - 1]); q--; } }二维数组前缀和
二维数组前缀和
public static void main(String[] args) { Scanner in = new Scanner(System.in); // 注意 hasNext 和 hasNextLine 的区别 while (in.hasNextInt()) { //写入数据 int n = in.nextInt(), m = in.nextInt(), q = in.nextInt(); int[][] arr = new int[n + 1][m + 1]; for (int i = 1 ; i <= n ; i++) { for (int j = 1 ; j <= m ; j++) { arr[i][j] = in.nextInt(); } } //预处理 dp 表示 1-1 到 i-j 的所有和 long[][] dp = new long[n + 1][m + 1]; for (int i = 1 ; i <= n ; i++) { for (int j = 1 ; j <= m ; j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i-1][j-1] + arr[i][j]; } } 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--; } } }避免越界 所以数组的创建 都是从（1，1）开始
寻找数组的中心下标
寻找数组的中心下标
public int pivotIndex(int[] nums) { int n = nums.length; int[] f = new int[n]; int[] g = new int[n]; //预处理 for(int i = 1; i<n; i++) f[i] = f[i - 1] + nums[i - 1]; for(int i = n - 2; i>=0; i--) g[i] = g[i + 1] + nums[i + 1]; // for(int i = 0 ;i<n ; i++){ if(f[i] == g[i]) return i; } return -1; }除了自身以外数组的乘积
除了自身以外数组的乘积
public int[] productExceptSelf(int[] nums) { int n = nums.length; int []j = new int[n]; int []q = new int[n]; //预处理 j[0] = q[n - 1 ] = 1; for(int i = 1; i<n; i++ ) j[i] = j[i - 1] * nums[i - 1]; for(int i = n - 2; i>=0;i--) q[i] = q[i + 1] * nums[i + 1 ]; // int [] ret = new int [n]; for(int i = 0; i<n; i++) ret[i] = q[i] * j[i]; return ret; }
