优选算法合集————双指针(专题四)

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=0;i–){ dp2[i] = dp2[i+1]+nums[i+1]; } for(int i = 0;i 和上一题一样，我们直接上图，注意细节，这道题原数组从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=0;i–){ dp2[i] = dp2[i+1]*nums[i+1]; } for(int i=0;i 这道题我们之前讲过一个方法叫滑动窗口，但是这道题不能用，因为这道题有负数，滑动窗口很适合单调的问题，所以我们要找其他的方法，这道题可以使用前缀和，

看这个图，我们从头到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 hash = new HashMap<>(); hash.put(0,1); for(int i=0;i 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 hash = new HashMap<>(); hash.put(0,1); for(int i =0;i

和前面两篇一样，注意细节问题，哈希表初始不是（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 hash = new HashMap<>(); hash.put(0,-1); for(int i=0;i

这道题我们要创建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; } }