双指针算法模板题目

水深无声 2024-03-26 12:38 76阅读 0赞

**题目来源：acwing算法基础课**

> **题目链接：**  
> [799. 最长连续不重复子序列 ][799. _]  
> **题目描述：**  
> ![在这里插入图片描述][4f16abbe794541338d3af13c5a9a7a3a.png]

**双指针（快慢指针）算法代码：**

#include<iostream>
    
    using namespace std;
    
    int a[100010],s[100010];
    
    int main()
    {
        
        int n;
        cin>>n;
        for(int i=0;i<n;++i) cin>>a[i];//输入
        
        int res=0;
        for(int i=0,j=0;i<n;i++)
        {
        
            s[a[i]]++;//循环遍历，把所有数字都存入到s数组里面
            while(j<i && s[a[i]]>1) --s[a[j++]];
            //当一个数字出现2次或者2以上 慢指针就要前进 从而 达到重新寻找
            //连续不重复子序列的目的。
            res=max(res,i-j+1);//不断比较从而迭代
        }
        cout<<res<<endl;
        return 0;
    }

> **题目链接：**  
> [800. 数组元素的目标和 ][800. _]  
> **题目描述：**  
> ![在这里插入图片描述][7218d2041dc142dc8cb5b84b8425ba77.png]

**双指针（对撞指针）算法代码：**

#include<iostream>
    
    using namespace std;
    
    int main()
    {
        
        int n,m,c;
        cin>>n>>m>>c;
        int a[100010],b[100010];
        for(int i=1;i<=n;++i) cin>>a[i];
        for(int j=1;j<=m;++j) cin>>b[j];//输入
        
        for(int i=1,j=m;i<=n;++i)//
        {
        
            while(j>=1 && a[i]+b[j]>c) j--;//比较大就j--也就是左移动
            if(j>=1&&a[i]+b[j]==c) 
            {
        
                printf("%d %d\n",i-1,j-1);
            }
        }
        return 0;
    }

**总结**  
问题：什么时候用快慢指针，什么时候用对撞指针？

你可以分析整体的单调性，或者模拟实现一下看看哪一个更加的合适。

双指针习题课 | 不听血亏 | 全新的思维方式

[799. _]: https://www.acwing.com/problem/content/801/
[4f16abbe794541338d3af13c5a9a7a3a.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/fd96f0860eb5408a8b03aa2ce47a61df.png
[800. _]: https://www.acwing.com/problem/content/802/
[7218d2041dc142dc8cb5b84b8425ba77.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/07642d4955264051af506735ee9c44c9.png