编辑
阿华代码，不是逆风，就是我疯
你们的点赞收藏是我前进最大的动力！！
希望本文内容能够帮助到你！！
目录
一：前缀和模版
编辑
编辑
import java.util.Scanner; // 注意类名必须为 Main, 不要有任何 package xxx 信息 public class Main { public static void main(String[] args) { Scanner in = new Scanner(System.in); //1：获取输入 int n = in.nextInt() , q = in.nextInt();//长度为n的数组，q次查询 int[] arr = new int[n+1]; for(int i = 1 ; i <= n ; i++){ arr[i] = in.nextInt(); } //2：创建dp数组 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() , r = in.nextInt(); System.out.println(dp[r]-dp[l-1]); q--; } } }
二：前缀和模版2
编辑
编辑 
编辑
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() , m = in.nextInt() , q = in.nextInt(); //arr数组 long[][] arr = 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(); } } //copy创建一个dp数组 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(); long result = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]; System.out.println(result); q--; } } }
三：寻找数组的中心下标
编辑
编辑
class Solution { public int pivotIndex(int[] nums) { int n = nums.length; //前缀和数组 int[] f = new int[n]; f[0] = 0; for(int i = 1 ; i < n ; i++){ f[i] = f[i-1] + nums[i-1]; } //后缀和数组 int[] g = new int[n]; g[n-1] = 0; for(int i = n-2 ; i >= 0 ; i--){ g[i] = g[i+1] + nums[i+1]; } int result = Integer.MAX_VALUE; for(int i = 0 ; i < n ; i++){ if(f[i] == g[i]){ result = Math.min(result,i); } } if(result == Integer.MAX_VALUE){ return -1; }else{ return result; } } }
四：除自身以外数组的乘积
238. 除自身以外数组的乘积 - 力扣（LeetCode）
编辑
编辑
class Solution { public int[] productExceptSelf(int[] nums) { int n = nums.length; //前缀积 int[] f = new int[n]; f[0] = 1; for(int i=1 ; i<n ; i++ ){ f[i] = f[i-1]*nums[i-1]; } int[] g = new int[n]; g[n-1] = 1; for(int i=n-2 ; i >= 0 ; i--){ g[i] = g[i+1]*nums[i+1]; } int[] answer = new int[n]; for(int i = 0 ; i < n ; i++){ answer[i] = f[i]*g[i]; } return answer; } }
五：和为K的子数组
编辑
编辑
class Solution { public int subarraySum(int[] nums, int k) { Map<Integer,Integer> hash = new HashMap<>(); hash.put(0,1); int sum = 0 , ret = 0; for(int x : nums){ sum += x; ret += hash.getOrDefault(sum-k,0); hash.put(sum,hash.getOrDefault(sum,0)+1); } return ret; } }
六：和被k整除的子数组
974. 和可被 K 整除的子数组 - 力扣（LeetCode）
编辑
编辑
class Solution { public int subarraysDivByK(int[] nums, int k) { Map<Integer,Integer> hashMap = new HashMap<Integer,Integer>(); hashMap.put(0 % k , 1);//默认有一个前缀和=0 int sum = 0;//前缀和 int ret = 0;//用来计数 for(int x : nums){ sum += x; int remainder = (sum % k + k) % k; ret += hashMap.getOrDefault(remainder,0); hashMap.put(remainder,hashMap.getOrDefault(remainder,0)+1); } return ret; } }
七：连续数组
编辑
编辑
class Solution { public int findMaxLength(int[] nums) { for(int i = 0 ; i < nums.length ; i++){ if(nums[i] == 0){ nums[i] = -1; } } Map<Integer,Integer> hash = new HashMap<>(); hash.put(0,-1); int sum = 0 , ret = 0; for(int i = 0 ; i < nums.length ; i++){ sum += nums[i]; if(hash.containsKey(sum)){ int old = hash.get(sum); int tem = i-old; ret = Math.max(ret,tem); }else{ hash.put(sum,i); } } return ret; } }
八：矩阵区域和
编辑
编辑
编辑
class Solution { public int[][] matrixBlockSum(int[][] mat, int k) { int m = mat.length , n = mat[0].length; //1：初始化dp前缀和数组 int[][] dp = new int[m+1][n+1]; for(int i = 1 ; i < m+1 ; i++){ for(int j = 1 ; j < n+1 ; j++){ dp[i][j] = dp[i-1][j] + dp[i][j-1] -dp[i-1][j-1] + mat[i-1][j-1]; } } //2:处理前缀和数组 int[][] ret = new int[m][n]; for(int i = 0 ; i < m ; i++){ for(int j = 0 ; j < n ; j++){ int x1 = Math.max(0,i-k)+1 , y1 = Math.max(0,j-k)+1; int x2 = Math.min(i+k,m-1)+1 , y2 = Math.min(j+k,n-1)+1; ret[i][j] = dp[x2][y2] - dp[x2][y1-1] -dp[x1-1][y2] + dp[x1-1][y1-1]; } } return ret; } }
