给定一个长度为n的整数序列,请找出最长的不包含重复的数的连续区间,输出它的长度。
输入格式
第一行包含整数n。
第二行包含n个整数(均在0~100000范围内),表示整数序列。
输出格式
共一行,包含一个整数,表示最长的不包含重复的数的连续区间的长度。
数据范围
1≤n≤100000
输入样例:
5
1 2 2 3 5
输出样例:
3
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+520;
ll A[N];
map<ll,ll>mp;
int main()
{
ll n;
cin>>n;
for(ll i=0;i<n;i++)cin>>A[i];
ll res=0;
for(ll i=0,j=0;i<n;i++)
{
mp[A[i]]++; //每次新加入一个元素,维护序列中此元素的个数加一;
while(j<=i&&mp[A[i]]>1) //判断新加入元素的个数在维护序列中的个数是否超过一个,
{ //如多于一个则由后往前删除;
mp[A[j]]--; //先删除;
j++; //后前移;
}
res=max(res,i-j+1); //更新最大值;
}
cout<<res<<endl;
}