双指针算法模板题目
2023-09-14 09:12:40 时间
题目来源:acwing算法基础课
题目链接:
799. 最长连续不重复子序列
题目描述:
双指针(快慢指针)算法代码:
#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. 数组元素的目标和
题目描述:
双指针(对撞指针)算法代码:
#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;
}
总结
问题:什么时候用快慢指针,什么时候用对撞指针?
你可以分析整体的单调性,或者模拟实现一下看看哪一个更加的合适。
双指针习题课 | 不听血亏 | 全新的思维方式
相关文章
- 【NLP基础】英文关键词抽取RAKE算法
- 性能和稳定性测试报告模板下载_产品稳定性报告怎样写
- gridview样式模板_css列表样式
- Latex 如何写算法?推荐模板
- zblog主题模板,水墨年华(filmslee)
- 个人博客主题模板中怎么插入第三方视频链接
- BFS算法模板与练习
- 【Android FFMPEG 开发】C++ 回调 Java 方法 模板 ( JavaVM *vm | JNIEnv *env | jobject instance | 引用类型 | 模板代码示例 )
- Spring Boot整合 Thymeleaf 模板引擎详解编程语言
- SQL Server 2019:快速实现企业高效开发的模板(sqlserver 模版)
- Win2003如何应用组策略和安全模板
- .netGridView分页模板的实例代码
- Zendstudio文件注释模板设置方法
- C#模板方法模式(TemplateMethodPattern)实例教程