双指针算法题目

题目1题目分析算法分析其他需要考虑的问题源代码 题目2题目说明算法解析源代码 双指针模板

题目1

给定一个长度为n的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。 输入格式 第一行包含整数n。 第二行包含n个整数（均在0~100000范围内），表示整数序列。 输出格式 共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。 数据范围 1≤n≤100000 输入样例： 5 1 2 2 3 5 输出样例： 3

题目分析

题目要求的是对输入的序列,找到那些满足:不包含重复的数的子序列,并记下来这些序列的长度,输出最长序列的长度.关键是如何遍历到所有的满足条件的子序列,

算法分析

本题使用的算法是双指针算法,双指针算法是简化版的朴素算法(暴力),朴素算法是直接两个嵌套循环从而遍历所有子序列,但是时间复杂度是O(n^2),双指针算法的出现是在找到规律的前提下,减少遍历的复杂度(也就是减少不必要的遍历). 现在分析题目:

首先建一个指针i,这是不论朴素还是双指针算法都必需的,将此指针作为另一个指针遍历的终点(也就是说i,j作为子序列的边界)现在先让指针i遍历,当指针i确定在某一个指针,那么另一个指针需要每次都从0开始遍历吗? 这里就是规律所在了,另一个指针其实只能向右走,而不能向左走,也就是说j的遍历完完全全不需要一个for循环来从头遍历,而只需要接着之前的位置走即可.*那么是为什么呢?*这里我们首先假设ij已经确定了自己的位置,即j的位置是以i为结尾的满足条件的最远位置.下一次遍历,i指针向右走,j指针可以前移吗?当然不能,因为前移表示的是此时的ij是满足条件的最大至值,而此区间其实包扩了 之前的i+前移的j,也就是说,前一个的选取出现了问题,这就出现了矛盾. 因此,j这个指针只能向右前进,而不需要从头遍历

其他需要考虑的问题

算法解决的是如何加快遍历的速度,但是如何确认i,j的位置,使得ij间没有重复的数字也没有解决. 这里使用的是一个数组S[],数组里存储的是当前区间内各个数字出现的次数,角标表示的是数字. 例如s[4]=2表示数字4在区间内出现了2次. 同时我们要知道,i的遍历是一定的,也就是说我们一直在寻找的其实是j的最佳位置.因此,其实区间的变化包含两部分:终点i向右移动1格,在此前提下起点j向右找满足条件的点.所以我们看到,其实数组区间先是增加了1个数q[i],如果重复一定是新增加的这个数重复,(当然没有重复是最好的,j不动区间是最大的),所以我们要做的是:

i向右移动1个位置,计数区间对应数的次数+1判断此时这个数的个数有没有大于1(大于1说明有两个此数)如果大于1,则j要向右移动,同时j所表示的数的个数-1,接着进行2的操作/如果没有大于1,说明没有重复,此时i的最大区间已经确定,就是i-j+1. //形象的比喻其实就是一个排队的通道,只能站不一样高的人,这时一个vip用户(比如175cm)直接站到队的最前面,如果大家都不一样高,那当然没问题,可如果不满足条件,就需要有人从队尾离开,队伍一直从后向前离开,直到队伍里除了vip的最后一个175离开才算结束.

源代码

import java.util.Scanner; class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int[] q=new int[100100]; int[] s=new int[100100]; int res=0; for(int i=0;i<n;i++){ q[i]=sc.nextInt(); } for(int i=0,j=0;i<n;i++){ s[q[i]]++; while(j<i&&s[q[i]]>1){//最后j会停在使i的数只有1个的位置 s[q[j]]--; j++; } res=Math.max(res,i-j+1); } System.out.print(res); } }

题目2

给定两个升序排序的有序数组A和B，以及一个目标值x。数组下标从0开始。 请你求出满足A[i] + B[j] = x的数对(i, j)。 数据保证有唯一解。 输入格式 第一行包含三个整数n，m，x，分别表示A的长度，B的长度以及目标值x。 第二行包含n个整数，表示数组A。 第三行包含m个整数，表示数组B。 输出格式 共一行，包含两个整数 i 和 j。 数据范围 数组长度不超过100000。 同一数组内元素各不相同。 1≤数组元素≤109 输入样例： 4 5 6 1 2 4 7 3 4 6 8 9 输出样例： 1 1

题目说明

给出两个有序且无重数组,并给出一个和,目的是找到两个数组中哪两个数的和等于给出的和,找到他们,返回他们的角标.

算法解析

同样是使用双指针算法.如果使用朴素算法,就是在第一个数组遍历,再嵌套一个第二个数组遍历.然而对于有序的数组,没有利用到这个条件就会浪费时间. 所以对于双指针算法的思维方式应该是这样:

首先无论是朴素还是双指针,必须有一个指针i,就叫他慢指针,慢指针从0开始,到数组未结束再寻找的时候,另一个快指针的选择从数组尾部开始,关键在于,j指针一定是只向左走,因为i指针是一直向右走,如果前一个i配合j都比x大,那么i向右走一定更比x大了,所以j只需要向左走即可

源代码

import java.util.Scanner; class Main{ public static void main(String[] args){ Scanner sc=new Scanner(System.in); int n=sc.nextInt(); int m=sc.nextInt(); int x=sc.nextInt(); int N=100100; int[] a=new int[N]; int[] b=new int[N]; for(int i=0;i<n;i++){ a[i]=sc.nextInt(); } for(int i=0;i<m;i++){ b[i]=sc.nextInt(); } int i,j; for(i=0,j=m-1;i<n;i++){ while(a[i]+b[j]>x&&j>0){ j--; } if(b[j]+a[i]==x) { break; } } System.out.print(i+" "+j); } }

双指针模板

for(int i=初始化,j=初始化;i<n;i++){ while(关于j的表达式的判断){ j进行移动}