算法思路：

1. 先预处理出来⼀个「前缀和」数组：

设前缀和数组为dp
dp[i] 表示： [1, i] 区间内所有元素的和，那么 dp[i - 1] 里面存的就是 [1, i - 1] 区间内所有元素的和，那么可得递推公式： dp[i] = dp[i - 1] + arr[i] ；

2. 使用前缀和数组，「快速」求出「某⼀个区间内」所有元素的和：

当询问的区间是 [l, r] 时：区间内所有元素的和为： 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);//1.读入数据int n = in.nextInt(), q = in.nextInt();int[] arr = new int[n+1];for(int i = 1; i <= n; i++) arr[i] = in.nextInt();//2.预处理一个前缀和数组long[] dp = new long[n+1];for(int i = 1; i <= n; i++) dp[i] = dp[i-1] + arr[i];//3.使用前缀和数组while(q > 0) {int l = in.nextInt(), r = in.nextInt();System.out.println(dp[r]-dp[l-1]);q--;}}
}

算法思路：
类比于⼀维数组，我们处理出来从 [0, 0] 位置到 [i, j] 位置这片区域内所有元素的累加和。

1. 预处理出来⼀个前缀和矩阵

下标直接从 1 开始

2. 前缀和矩阵中 dp[i][j] 的含义，以及如何递推二维前缀和方程

dp[i][j] 表示，从 [1, 1] 位置到 [i, j] 位置这段区域内，所有元素的累加和
递推方程：
我们可以将 [1, 1] 位置到 [i, j]位置这段区域分解成下面的部分：

整个面积 = A+B+C+D = (A+B) + (A+C) + D - A = dp[i-1][j] + dp[i][j-1] + arr[i][j] - dp[i-1][j-1]
接下来分析如何使用这个前缀和矩阵
我们要求的就是A的面积:
A = 整个面积 - （C + D）- （B + D）+ D = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

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(), 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();}}//2.预处理一个前缀和矩阵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]+arr[i][j]-dp[i-1][j-1];}}//3.使用前缀和矩阵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--;}}
}

算法思路：
由中心下标的定义可知，除中心下标的元素外，该元素左边的「前缀和」等于该元素右边的「后缀和」。

• 因此，我们可以先预处理出来两个数组，⼀个表示前缀和，另⼀个表示后缀和。
• 然后，我们可以用⼀个 for 循环枚举可能的中心下标，判断每⼀个位置的「前缀和」以及「后缀和」，如果二者相等，就返回当前下标。

class Solution {public int pivotIndex(int[] nums) {int n = nums.length;int[] f= new int[n];int[] g= new int[n];//1.预处理一下前缀和数组以及后缀和数组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];}//2.使用for(int i = 0; i < n; i++) {if(f[i] == g[i]) {return i;}}return -1;}
}

还可以这样:

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

算法思路：
注意题目的要求，不能使用除法，并且要在 O(N) 的时间复杂度内完成该题。那么我们就不能使用暴力的解法，以及求出整个数组的乘积，然后除以单个元素的方法(元素如果有0的话还得特殊讨论)。

根据题意，对于每⼀个位置的最终结果 ret[i] ，它是由两部分组成的：

1. nums[0] * nums[1] * nums[2] * … * nums[i - 1]
2. nums[i + 1] * nums[i + 2] * … * nums[n - 1]

于是，我们可以利用前缀和的思想，使用两个数组 f 和 g，分别处理出来两个信息：

• f 表示：i 位置之前的所有元素的前缀乘积，
• g表示： i 位置之后的所有元素的后缀乘积

然后再处理最终结果。

class Solution {public int[] productExceptSelf(int[] nums) {int n = nums.length;int[] f = new int[n];int[] g = new int[n];//1.预处理前缀积数组以及后缀积数组f[0] = g[n-1] = 1;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];}//2.使用int[] ret = new int[n];for(int i = 0; i < n ; i++) {ret[i] = f[i] * g[i];}return ret;}
}

简化版本:

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

因为元素中有0和负数,不能用滑动窗口解决

算法思路：

设 i 为数组中的任意位置，用 sum[i] 表示 [0, i] 区间内所有元素的和。
想知道有多少个「以 i 为结尾的和为 k 的子数组」，就要找到多少个起始位置为 x 使得 [x, i] 区间内所有元素的和为 k 。那么 [0, x - 1] 区间内的和就是sum[i] - k 了。于是问题就变成：找到 [0, i - 1] 区间内，有多少前缀和等于 sum[i] - k 即可。
我们不用真的初始化⼀个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于sum[i] - 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;}
}

本题需要的前置知识：

• 同余定理

如果 (a - b) % n == 0 ，那么我们可以得到⼀个结论： a % n == b % n 。
因为(a - b) % n == 0, 所以 (a -b) ÷ n = k , 也就是a = b+ n × k, 两边同时%n
得到a % n == b % n

• Java 中负数取模的结果，以及如何修正「负数取模」的结果:

Java 中关于负数的取模运算，结果是「把负数当成正数，取模之后的结果加上⼀个负号」。

	public static void main(String[] args) {System.out.println(-7%3);}

为了防止「出现负数」，以 (a % n + n) % n 的形式保证输出为正。

	public static void main(String[] args) {System.out.println((-7%3+3)%3);}

算法思路：

思路与和为 K 的子数组相似。
设 i 为数组中的任意位置，用sum[i] 表示 [0, i] 区间内所有元素的和。

• 想知道有多少个「以 i 为结尾的可被 k 整除的子数组」，就要找到多少个起始位置为 x使得 [x, i] 区间内所有元素的和可被 k 整除。
• 设 [0, x - 1] 区间内所有元素之和等于 a ， [0, i] 区间内所有元素的和等于 b ，可得
  (b - a) % k == 0 。
• 由同余定理可得， [0, x - 1] 区间与 [0, i] 区间内的前缀和同余。于是问题就变成：找到[0, i - 1] 区间内，有多少前缀和k的余数等于 sum[i] % k 的即可。
• 我们不用真的初始化⼀个前缀和数组，因为我们只关心在 i 位置之前，有多少个前缀和等于sum[i] % k 。因此，我们仅需用⼀个哈希表，⼀边求当前位置的前缀和，⼀边存下之前的前缀和。

class Solution {public int subarraysDivByK(int[] nums, int k) {Map<Integer, Integer> hash = new HashMap<>();hash.put(0 % k, 1);int sum = 0, ret = 0;for(int x: nums){sum += x;int r = (sum % k + k) % k;ret += hash.getOrDefault(r, 0);hash.put(r, hash.getOrDefault(r, 0) + 1);}return ret;}
}

算法思路：

本题让我们找出⼀段连续的区间， 0 和 1 出现的次数相同。

• 如果将 0 记为 -1 ， 1 记为 1 ，问题就变成了找出⼀段区间，这段区间的和等于 0 。
• 于是，就和 和为 K 的子数组 的思路⼀样

设 i 为数组中的任意位置，用 sum[i] 表示 [0, i] 区间内所有元素的和。

想知道最大的「以 i 为结尾的和为 0 的子数组」，就要找到 x 使得 [x, i]区间内的所有元素的和为 0 。那么 [0, x - 1] 区间内元素的和就是 sum[i] 了。于是问题就变成：找到在 [0, i - 1] 区间内，第⼀次出现 sum[i] 的位置即可。
我们不用真的初始化⼀个前缀和数组，我们只关心在 i 位置之前，第⼀个前缀和等于 sum[i]的位置。因此，我们仅需用⼀个哈希表，⼀边求当前位置的前缀和，⼀边记录第⼀次出现该前缀和的位置。

class Solution {public int findMaxLength(int[] nums) {Map<Integer, Integer> hash = new HashMap<>();hash.put(0, -1);//默认存在一个前缀和为0的情况int sum = 0, ret = 0;for(int i = 0; i < nums.length; i++) {sum += (nums[i] == 0 ? -1 : 1);//计算当前位置的前缀和if(hash.containsKey(sum)) ret = Math.max(ret, i - hash.get(sum));else hash.put(sum, i);}return ret;}
}

算法思路：

二维前缀和，关键是找到原矩阵对应区域的「左上角」以及「右下角」的坐标（推荐大家画图）
左上角坐标： x1 = i - k，y1 = j - k ，但是由于会「超过矩阵」的范围，因此需要和 0 比较取⼀个 max 。

右下角坐标： x2 = i + k，y2 = j + k ，但是由于会「超过矩阵」的范围，因此需要比较 m - 1 以及 n - 1 取⼀个 min 。因此修正后的坐标为： x2 = min(m - 1, i + k), y2 = min(n - 1, j + k) 。

然后将求出来的坐标代⼊到「二维前缀和矩阵」的计算公式上即可

class Solution {public int[][] matrixBlockSum(int[][] mat, int k) {int m = mat.length, n = mat[0].length;//1.预处理前缀和矩阵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] = 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(m-1, i + k) + 1, y2 = Math.min(n-1, j+k) + 1;ret[i][j] = dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]; }}return ret;}
}