---

前缀和题目练习

前缀和

自己写出来了~

坑:

• 数据太大,要用long.

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

题解代码:

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();long[] arr = new long[n+1];long[] dp = new long[n+1];for(int i=1;i<=n;i++) {arr[i] = in.nextLong();dp[i] = arr[i] + dp[i-1];}while(q-- > 0){int l = in.nextInt();int r = in.nextInt();System.out.println(dp[r]-dp[l-1]);}}
}

二维前缀和

自己写出来了~

在往二维数组存数据的时候,内层循环用错了,应该用 m,而不是 n.
在最后计算结果的时候,最开始没有算的太明白.

dp[i][j] 计算的是它左上方所有元素的和(包括自己)~

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();long[][] arr = new long[n+1][m+1];long[][] dp = 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++) {dp[i][j] = dp[i][j-1]+dp[i-1][j]-dp[i-1][j-1]+arr[i][j];// System.out.printf("%d ",dp[i][j]);}// System.out.println();}while(q-- > 0) {int x1 = in.nextInt();int y1 = in.nextInt();int x2 = in.nextInt();int y2 = in.nextInt();System.out.println(dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1]);}}
}

寻找数组的中心下标

我的第一反应是想用一个sum计算所有元素的和,然后除 2 得到 target,接着再使用滑动窗口寻找这个target , 发现行不通,因为数组中可能有负数和0~

自己写出来了~

坑:

• 题目说: 如果有结果,返回最靠左的那一个~

class Solution {public int pivotIndex(int[] nums) {int[] dp = new int[nums.length];dp[nums.length - 1] = nums[nums.length - 1];for (int i = nums.length - 2; i >= 0; i--) {dp[i] = dp[i + 1] + nums[i];}int sum = 0;for (int i = 0; i < nums.length; i++) {sum += nums[i];if (sum == dp[i])return i;}return -1;}
}

除自身以外数组的乘积

自己写出来了~
优化前(空间复杂度 O(N) ):

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

优化后(空间复杂度 O(1) ):

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] ret = new int[n];// 计算前面元素的乘积ret[0] = nums[0];for (int i = 1; i < n - 1; i++) {ret[i] = ret[i - 1] * nums[i];}ret[n - 1] = ret[n - 2];// 用sum表示后面元素的乘积int sum = nums[n - 1];for (int i = n - 2; i > 0; i--) {ret[i] = ret[i - 1] * sum;sum *= nums[i];}ret[0] = sum;return ret;}
}

和为 K 的子数组

因为数组中的元素有小于等于0的数,所以不能使用滑动窗口来解题~

没写出来.

1. 在 [0 , i - 1] 区间内,有多少个前缀和等于 sum[i] - k
2. 使用哈希表<前缀和,出现次数>
   

• 1,2 都懂, 到 3 的时候有点晕.

    class Solution {public int subarraySum(int[] nums, int k) {int n = nums.length;HashMap<Integer, Integer> hash = new HashMap<>();int ret = 0;int sum = 0;hash.put(0, 1);for (int i = 0; i < n; i++) {sum += nums[i];ret += hash.getOrDefault(sum - k, 0);hash.put(sum, hash.getOrDefault(sum, 0) + 1);}return ret;}}

和可被 K 整除的子数组

没写出来,但是写了个大概,就差一点,
就差 sum = (sum % k + k) % k; 这一句话…

遇到取余就满头包~

每日LeetCode,974. 和可被 K 整除的子数组

写这道题需要知道两个前置知识.

1. 同余定理
   如果 (a - b) % n == 0 那么我们可以得到一个结论: a % n == b % n.

2. 修正负数取模的结果
   为了防止出现负数的情况,可以使用 (a % n + n) % n 的形式保证输出结果为正.

    public int subarraysDivByK(int[] nums, int k) {int sum = 0;int ret = 0;int n = nums.length;HashMap<Integer, Integer> hash = new HashMap<>();hash.put(0, 1);for (int i = 0; i < n; i++) {sum += nums[i];sum = (sum % k + k) % k;ret += hash.getOrDefault(sum, 0);hash.put(sum, hash.getOrDefault(sum, 0) + 1);}return ret;}

连续数组

这一次 HashMap 中存的就不是数字出现的次数了,而是数字出现的下标.

class Solution {public int findMaxLength(int[] nums) {int ret = 0;int n = nums.length;HashMap<Integer,Integer> hash = new HashMap<>();int sum = 0;hash.put(0,-1);for(int i=0;i<n;i++) {sum += nums[i] == 0?-1:1;if(hash.containsKey(sum)) {ret = Math.max(ret,i - hash.get(sum));}else {// 当不包含 sum 时,放进hash中// 当 hash 中已经包含 sum 时,不必再放入// ret = i - hash.get(sum)// 我们要求的是最大值,因此hash.get(sum)越小越好,// 而新 put 进来的下标i 一定没有 之前的下标小// 也就是说新的hash.get(sum)比旧的hash.get(sum)大 // 用一句话概括:// 当 hash 中已经包含 sum 时,此时再更新i的话 ret 会变小// 因此要写 elsehash.put(sum,i);}}return ret;}
}

矩阵区域和

坑;

• 范围容易找错
  

• 如果善用 Math 方法更好一点~

class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {int m = mat.length;int n = mat[0].length;int[][] ret = new int[m][n];int[][] dp = new int[m+1][n+1];for (int i = 1; i <= m; i++) {for (int j = 1; j <= n; j++) {dp[i][j] = mat[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1];}}for (int i = 0; i < m; i++) {for (int j = 0; j < n; j++) {int a = Math.min(i+k+1,m);int b = Math.min(j+k+1,n);int c = Math.max(i-k+1,1);int d = Math.max(j-k+1,1);ret[i][j] = dp[c-1][d-1] - dp[c-1][b] - dp[a][d-1] + dp[a][b];}}return ret;}
}

---

本文到这里就结束啦~