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] <= 104
• 2 <= 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 <= 105
• nums[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.length
• n == mat[i].length
• 1 <= m, n, k <= 100
• 1 <= 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;}
}

 

---