双指针思维导图_编号w856511-TreeMind树图

笔灵AI论文写作三步搞定，GO>>

当前位置:树图

思维导图模板

高校与高等教育

其他学科

双指针思维导图

免费下载

免费使用文件

Mr.Xu

浏览量：1

2023-07-13 18:41:39

已被使用0次

查看详情

双指针

树图思维导图提供双指针在线思维导图免费制作，点击“编辑”按钮，可对双指针进行在线思维导图编辑，本思维导图属于思维导图模板主题，文件编号是：884cd86ff6eff9c3eb62493dbc8f69f0

双指针算法

举报/反馈

思维导图大纲

双指针思维导图模板大纲

有一些问题，我们用常规方法是会超时的，但这是我们又很难用一些高级的算法写出来时，就可以想一想能不能用双指针来遍历

顾名思义，就是用两个指针来遍历整个数组找到解，一般有两种方法。1.两个指针一起从头遍历2.两个指针一头一尾遍历。切记：这里指针时不走回头路的，要不然时间又和常规方法一样了，就没有什么意义了。

例题1

最长连续不重复子序列给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度[数据范围] 1<n<100000

显然用常规方法双重循环肯定会超时，这时候我们就可以用双指针，这里就属于第一种，具体思路为：定义两个指针i,j每次i线往后走，如果出现重复的，j再往后走，然后用一个最大值变量存长度。判断重复的话就可以用桶标记

#include<bits/stdc++.h> using namespace std; const int N=1e5+10; int a[N],f[N],maxn=-1; int main(){ int n; scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1,j=1;i<=n;i++){ f[a[i]]++; while(f[a[i]]>1){ f[a[j]]--; j++; } maxn=max(i-j+1,maxn); } cout<<maxn; return 0; }

例题2

和为指定值给定两个升序排序的有序数组 A和 B，以及一个目标值X。数组下标从0开始。请你求出满足 A[i]+B[j]=x 的数对(i,j)。数组长度不超过 10^5。同一数组内元素各不相同。1<数组元素<10^9

这里我们用到的就是第二种，具体思路为：第一两个指针i=1,j=m如果a[i]+b[j]>x将j--，小于的话i++直到找到解。因为他说了，这是两个有序数组，所以可以这样，如果没说的话自己排个序就行了，边界是i<=n&&j>=1

#include<bits/stdc++.h> using namespace std; const int N=1e5+5; int a[N],b[N]; int main(){ int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=m;i++) scanf("%d",&b[i]); int i=1,j=m; while(i<=n&&j>=1){ if(a[i]+b[j]==k){ printf("%d %d\n",i-1,j-1); i++; j--; } else if(a[i]+b[j]>k) j--; else i++; } return 0; }