【算法】——前缀和（矩阵区域和详解，文末附）
阿华代码，不是逆风，就是我疯
你们的点赞收藏是我前进最大的动力！！
希望本文内容能够帮助到你！！
目录
一：前缀和模版
二：前缀和模版2
三：寻找数组的中心下标
四：除自身以外数组的乘积
五：和为K的子数组
六：和被k整除的子数组
七：连续数组
八：矩阵区域和
一：前缀和模版
【模板】前缀和_牛客题霸_牛客网
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--;}}
}三：寻找数组的中心下标
724. 寻找数组的中心下标 - 力扣（LeetCode）
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的子数组
560. 和为 K 的子数组 - 力扣（LeetCode）
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);//默认有一个前缀和=0int 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;}
}七：连续数组
525. 连续数组 - 力扣（LeetCode）
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;}
}八：矩阵区域和
1314. 矩阵区域和 - 力扣（LeetCode）
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;}
}