题目描述
最长连续不重复子序列
给定一个长度为n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
C++ 代码
#include<iostream>
using namespace std;
const int N=100010;
int a[N],s[N];
int n;
int main()
{
cin>>n;
for(int i=0;i<N;i++)
cin>>a[i];
//res表示最长长度
int res=0;
//使用双指针:i用来遍历整个原数组,代表不重复数列的终止位置.j代表不重复数列的起始位置
for(int i=0,j=0;i<n;i++)
{
s[a[i]]++; //s[]数组用来记录重复数字的个数
//当有重复数字时
while(s[a[i]]>1)
{
s[a[j]]--; //从该重复数字之前的数字都不算数,该重复数字的数量一直减到1个
j++; //直到j移动到该重复数字上,至重复数字的数量减为1
}
res=max(res,i-j+1); //将最大长度赋值给res,因为数组是从0开始的,所以最后要+1
}
cout<<res;
return 0;
}