双指针——最长不重复连续子序列
题目描述
给定一个长度为 n 的整数序列，请找出最长的不包含重复的数的连续区间，输出它的长度。
输入格式
第一行包含整数 n。
第二行包含 n 个整数（均在 0∼10^5 范围内），表示整数序列。
输出格式
共一行，包含一个整数，表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤10^5
输入样例
5
1 2 2 3 5输出样例
3注释版代码
#include<iostream>
using namespace std;
const int N=100010;//因为数据范围为10^5，若使用暴力做法，两层循环时间复杂度为n²，所以使用双指针复杂度为n
int n,res;
int q[N],s[N];//s[]来统计i到j中某一字符出现的次数，当他出现1次以上即为重复
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
{
scanf("%d",&q[i]);
}
for(int i=0,j=0;i<n;i++)
{
s[q[i]]++;//先将每一个q[i]出现的次数+1
while(j<i&&s[q[i]]>1)//当j在i的左边，并且q[i]出现的次数大于1了，那么也就是说刚输入的q[i]一定是和j这个指针重了
{
s[q[j]]--;//那我们接下来的操作就是要将j后移了
//a[i]进来之后就有重复元素了，我们要从前往后去掉，直到没有重复元素，所以我们将s[q[j]]--
j++;//紧接着我们将j后移
}
res=max(res,i-j+1);
}
printf("%d",res);
return 0;
}原文地址：https://blog.csdn.net/r2931887650/article/details/142727440
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！