1，一维前缀和模版
题目描述：
描述
给定一个长度为n的数组a1,a2,....ana1,a2,....an.
接下来有q次查询, 每次查询有两个参数l, r.
对于每个询问, 请输出al+al+1+....+aral+al+1+....+ar
输入描述：
第一行包含两个整数n和q.
第二行包含n个整数, 表示a1,a2,....ana1,a2,....an.
接下来q行,每行包含两个整数 l和r.
1≤n,q≤1051≤n,q≤105
−109≤a[i]≤109−109≤a[i]≤109
1≤l≤r≤n1≤l≤r≤n
输出描述：
输出q行,每行代表一次查询的结果.
示例1
输入：
3 2 1 2 4 1 2 2 3
复制输出：
3 6
题目解析：
这道题是前缀和的典型模版，前缀和是什么的，从头开始到当前下标前面所有元素的累加，我们可以把前缀和抽象成一个公式，
这里大家一定一定不能混淆，dp[0]并不是从0下标开始的， 因为dp公式i为0的时候dp[i-1]是不存在的，我们只能从dp[1]开始，dp[1]才是真正对应arr[]数组的0下标，dp公式是怎么来的呢，我们可以观察到，dp[i]的值都是由当前arr[i]的元素和前一个下标的前缀和组成的，
算法思路：
直接初始化前缀和公式，使用前缀和公式快速求值；
这道题有一些细节问题，题目中要求的是a1到an的值我们从零下标开始拷贝到数组中时不行的，所以我们初始化数组的时候容量要设置为[n+1]；
代码实现：
public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int 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 l = in.nextInt();
int r = in.nextInt();
q--;
System.out.println(dp[r]-dp[l-1]);
}
}
}2，二维前缀和模版
题目描述：
描述
给你一个 n 行 m 列的矩阵 A ，下标从1开始。
接下来有 q 次查询，每次查询输入 4 个参数 x1 , y1 , x2 , y2
请输出以 (x1, y1) 为左上角 , (x2,y2) 为右下角的子矩阵的和，
输入描述：
第一行包含三个整数n,m,q.
接下来n行，每行m个整数，代表矩阵的元素
接下来q行，每行4个整数x1, y1, x2, y2，分别代表这次查询的参数
1≤n,m≤10001≤n,m≤1000
1≤q≤1051≤q≤105
−109≤a[i][j]≤109−109≤a[i][j]≤109
1≤x1≤x2≤n1≤x1≤x2≤n
1≤y1≤y2≤m1≤y1≤y2≤m
输出描述：
输出q行，每行表示查询结果。
示例1
输入：
3 4 3 1 2 3 4 3 2 1 0 1 5 7 8 1 1 2 2 1 1 3 3 1 2 3 4
复制输出：
8 25 32
题目解析：
这道题给了我们一个n行m列的矩阵，我们要进行q次查询，每次查询输入4个数，分别是x1,y1,x2,y2,我们要根据这4个下标求出（y2-y1+1）*（x2-x1+1）这一区域所有元素的和；
算法思路：
暴力解法绝对不可能了，每次找数都是O(n2)的时间复杂度的，q次查询，如果q很大我们根本承担不起，我们引出二维前缀和，这题就是个典型模版，二维前缀和就是从1,1位置到（x，y）位置的所有和，那么这道题怎么解呢：
1，列出二维前缀和的状态转移方程
2，指定我们要的区域列出新的方程
这道题还是从1开始的，所以我们dp方程和二维数组是对应的，如果二维数组是0的话就要考虑考虑了；
这里我直接用纸写了，太懒了；
代码实现：
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();
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();
}
}
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][j-1]+dp[i-1][j]+arr[i][j]-dp[i-1][j-1];
}
}
while(q>=1){
int x1 = in.nextInt();
int y1 = in.nextInt();
int x2 = in.nextInt();
int y2 = in.nextInt();
q--;
long a = dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];
System.out.println(a);
}
}
}3，寻找数组的中心下标
题目描述：
给你一个整数数组 nums ，请计算数组的 中心下标 。
数组 中心下标 是数组的一个下标，其左侧所有元素相加的和等于右侧所有元素相加的和。
如果中心下标位于数组最左端，那么左侧数之和视为 0 ，因为在下标的左侧不存在元素。这一点对于中心下标位于数组最右端同样适用。
如果数组有多个中心下标，应该返回 最靠近左边 的那一个。如果数组不存在中心下标，返回 -1 。
示例 1：
输入：nums = [1,7,3,6,5,6] 输出：3 解释： 中心下标是 3 。 左侧数之和 sum = nums[0] + nums[1] + nums[2] = 1 + 7 + 3 = 11 ， 右侧数之和 sum = nums[4] + nums[5] = 5 + 6 = 11 ，二者相等。
示例 2：
输入：nums = [1, 2, 3] 输出：-1 解释： 数组中不存在满足此条件的中心下标。
示例 3：
输入：nums = [2, 1, -1] 输出：0 解释： 中心下标是 0 。 左侧数之和 sum = 0 ，（下标 0 左侧不存在元素）， 右侧数之和 sum = nums[1] + nums[2] = 1 + -1 = 0 。
题目解析：
这道题给了我们一个数组，我们要找到一个下标，使得该下标两边的值都相等。如果使用暴力方法的话，首先要遍历每一个元素，在向左向右遍历是不是相等，时间复杂度为O(n2)，那么有没有更简单的方法呢；
算法思路：
这道题我们随便找一个中心下标，左边不就是从头开始到当前i-1元素的前缀和吗，后边我们可以反过来看，是一个从末尾到i+1元素的后缀和，所以我们可以写两个dp数组，值进行一次循环遍历，看看当前下标的两个元素和是否相等，我还是用手写来给大家创建一下前缀和；
代码实现：
class Solution {
public int pivotIndex(int[] nums) {
int n = nums.length;
int[] dp1 = new int[n];
int[] dp2 = new int[n];
dp1[0] = 0;
dp2[0] = 0;
for(int i=1;i<n;i++){
dp1[i] = dp1[i-1]+nums[i-1];
}
for(int i=n-2;i>=0;i--){
dp2[i] = dp2[i+1]+nums[i+1];
}
for(int i = 0;i<n;i++){
if(dp1[i]==dp2[i]){
return i;
}
}
return -1;
}
}4，除自身以外数组的乘积
题目描述：
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请 不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1:
输入: nums =[1,2,3,4]输出:[24,12,8,6]
示例 2:
输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 105-30 <= nums[i] <= 30- 输入 保证 数组
answer[i]在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）
题目解析：
这道题跟刚才那道题一模一样，给我们一个数组，把除当前下标的所有乘积放到新数组中，那就是左前缀积和右前缀积；
算法思路：
和上一题一样，我们直接上图，注意细节，这道题原数组从0开始；
代码实现：
class Solution {
public int[] productExceptSelf(int[] nums) {
int n = nums.length;
int[] dp1 = new int[n];
int[] dp2 = new int[n];
int[] answer = new int[n];
dp1[0] = 1;
dp2[n-1] = 1;
for(int i = 1;i<n;i++){
dp1[i] = dp1[i-1]*nums[i-1];
}
for(int i = n-2;i>=0;i--){
dp2[i] = dp2[i+1]*nums[i+1];
}
for(int i=0;i<n;i++){
answer[i] = dp1[i]*dp2[i];
}
return answer;
}
}5，和为k的子数组
题目描述：
给定一个整数数组和一个整数 k ，请找到该数组中和为 k 的连续子数组的个数。
示例 1：
输入:nums = [1,1,1], k = 2 输出: 2 解释: 此题 [1,1] 与 [1,1] 为两种不同的情况
示例 2：
输入:nums = [1,2,3], k = 3 输出: 2
提示:
1 <= nums.length <= 2 * 104-1000 <= nums[i] <= 1000-107 <= k <= 107
题目解析：
这道题给了我们一个数组和一个元素k，我们要找到连续且和为k的子数组的个数，
算法思路：
这道题我们之前讲过一个方法叫滑动窗口，但是这道题不能用，因为这道题有负数，滑动窗口很适合单调的问题，所以我们要找其他的方法，这道题可以使用前缀和，
看这个图，我们从头到i下标的前缀和是sum，其中某一个元素j的前缀和为sum-k，那么此时i下标到j下标之后这一段区域不就是k吗，那么我们要创建前缀和数组，用两层循环来一个一个判断i到j的和是k吗，那么我们还不如暴力解决它，当我们从i下标开始找sum-k的时候sum-k是可能存在多个的，我们可以把问题转化成我们从i下标开始，找到sum-k出现的次数，我们可以使用哈希表来记录，前缀和出现的次数，我们每次添加的前缀和都是不同j位置的，我们遍历i的时候，去哈希表寻找sum-k出现的次数，就是寻找有多少个j下标与当前i下标是能够构成dp[i]-dp[j-1]的；
我们还要先往哈希表中放个0，怕我们i为n-1的时候前缀和就为k，那sum-k就为0了；
代码实现：
class Solution {
public int subarraySum(int[] nums, int k) {
int sum = 0;
int count = 0;
HashMap<Integer,Integer> hash = new HashMap<>();
hash.put(0,1);
for(int i=0;i<nums.length;i++){
sum+=nums[i];
count+=hash.getOrDefault(sum-k,0);
hash.put(sum,hash.getOrDefault(sum,0)+1);
}
return count;
}
}6，和可以被k整除的子数组
题目描述：
给定一个整数数组 nums 和一个整数 k ，返回其中元素之和可被 k 整除的非空 子数组 的数目。
子数组 是数组中 连续 的部分。
示例 1：
输入：nums = [4,5,0,-2,-3,1], k = 5 输出：7 解释： 有 7 个子数组满足其元素之和可被 k = 5 整除： [4, 5, 0, -2, -3, 1], [5], [5, 0], [5, 0, -2, -3], [0], [0, -2, -3], [-2, -3]
示例 2:
输入: nums = [5], k = 9 输出: 0
提示:
1 <= nums.length <= 3 * 104-104 <= nums[i] <= 1042 <= k <= 104
题目解析：
这道题和上一题基本一样，但是这道题我们有两个需要掌握的知识；
算法思路：
1，同余定理
如果(a-n)%p = k(0) 那么a%p=n%p；
2，java中保证负数取模为正数 （a%p+p）%p；
感兴趣可以搜一下怎么推出来的，我们用就好了；
我们知道从头开始到i和从头开始到j的前缀和，当sum-x可以整除k的时候，用同余定理就意味着sum%k = x%k，所以我们就可以把问题转化成当为i下标时，找到与sum%k相等的前缀和%k，
代码实现：
class Solution {
public int subarraysDivByK(int[] nums, int k) {
int sum = 0;
int count = 0;
HashMap<Integer,Integer> hash = new HashMap<>();
hash.put(0,1);
for(int i =0;i<nums.length;i++){
sum+=nums[i];
count+=hash.getOrDefault((sum%k+k)%k,0);
hash.put((sum%k+k)%k,hash.getOrDefault((sum%k+k)%k,0)+1);
}
return count;
}
}7，连续数组
题目描述：
给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例 1：
输入：nums = [0,1] 输出：2 说明：[0, 1] 是具有相同数量 0 和 1 的最长连续子数组。
示例 2：
输入：nums = [0,1,0] 输出：2 说明：[0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。
示例 3：
输入：nums = [0,1,1,1,1,1,0,0,0] 输出：6 解释：[1,1,1,0,0,0] 是具有相同数量 0 和 1 的最长连续子数组。
提示：
1 <= nums.length <= 105nums[i]不是0就是1
题目解析：
我们可以把所有的0，看成-1，这样就是找和为0的子数组了；
这道题呢和前面两道题差不多，但是我们找的不是子数组个数了，而是找下标，
算法思路：
和前面两篇一样，注意细节问题，哈希表初始不是（0,1）了，当i为n-1时，前缀和为0，那么说明sum-0，的下标为-1；也就是没有；长度的计算问题，是i-j，
代码实现：
class Solution {
public int findMaxLength(int[] nums) {
int sum= 0;
int ret = 0;
HashMap<Integer,Integer> hash = new HashMap<>();
hash.put(0,-1);
for(int i=0;i<nums.length;i++){
sum += nums[i]==0?-1:1;
if(hash.containsKey(sum)) ret = Math.max(ret,i-hash.getOrDefault(sum,0));
else hash.put(sum,i);
}
return ret;
}
}这里要注意，因为我们找的是最大长度，所以我们只记录第一个符合条件的元素，因为此时能保证
i-j是最大的，当我们再次找到sum的时候，说明我们之前已经遇到过了，不需要再添加的哈希表了，我们没遇到的时候才把它添加的哈希表中，为了保证每次都是从最左边的开始，算最大的长度；
8，矩阵区域和
题目描述：
给你一个 m x n 的矩阵 mat 和一个整数 k ，请你返回一个矩阵 answer ，其中每个 answer[i][j] 是所有满足下述条件的元素 mat[r][c] 的和：
i - k <= r <= i + k,j - k <= c <= j + k且(r, c)在矩阵内。
示例 1：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 1 输出：[[12,21,16],[27,45,33],[24,39,28]]
示例 2：
输入：mat = [[1,2,3],[4,5,6],[7,8,9]], k = 2 输出：[[45,45,45],[45,45,45],[45,45,45]]
提示：
m == mat.lengthn == mat[i].length1 <= m, n, k <= 1001 <= mat[i][j] <= 100
题目解析：
这道题给了我们一个mat数组，我们要往answer数组中填写根据mat数组改写的一些数据，具体怎么改写呢，题目给了一个k，我们要根据mat数组上下左右都扩充一个k长度，里面所有数据的和填到answer数组中，太明显了，二维前缀和；
算法思路：
这道题我们要创建dp数组，根据原数组来创建dp数组，要注意我们原数组是从0下标开始的，而dp数组是从1，1开始的，所以我们dp数组创建时m，n都要加1，dp数组创建完之后我们就要，根据原数组往answer数组填东西了，我们还记得二维前缀和模版吗，我们求D区域的和就是从坐上下标到右下下标区域的和，这道题也是一样的，左上标是（i-1，j-1）右下标是（i+1，j+1），我们避免越界要在左上取max（0，-）右下（m-1，-）；这样就能避免越界啦，填入的时候也要考虑下标的对应问题；
代码实现：
class Solution {
public int[][] matrixBlockSum(int[][] mat, int k) {
int m = mat.length;
int n = mat[0].length;
int[][] answer = 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] = dp[i][j-1]+dp[i-1][j]+mat[i-1][j-1]-dp[i-1][j-1];
}
}
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
int x1 = Math.max(0,i-k)+1;
int y1 = Math.max(0,j-k)+1;
int x2 = Math.min(m-1,i+k)+1;
int y2 = Math.min(n-1,j+k)+1;
answer[i][j] = dp[x2][y2] - dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];
}
}
return answer;
}
}