思路:
本题数据规模较大,应采用双指针+哈希表
使用两个指针i,j(i > j)如果没有重复元素:更新长度,否则队首元素个数-1,首指针++
可以用STL中的哈希表,也可以手写哈希表(手写1000多秒,STL5000多秒)
上代码
#include <iostream>
#include <map>
#include <cstring>
using namespace std;
const int N = 2000003,null = 0x3f3f3f3f; // 对质数取模
int n,h[N],a[N];
int ans = 0;
map<int,int> hash;
void STL(){
for(int i=0,j=0;i<n;i++){
hash[a[i]]++;
while(j < i && hash[a[i]] > 1) hash[a[j++]] -- ;
ans = max(ans,i - j + 1);
}
printf("%d",ans);
}
int find(int x)
{
int t=(x%N+N)%N;
while(h[t]!=null and h[t]!=x)
{
t++;
if(t==N) t=0;
}
return t;
}
void solve(){
memset(h,0x3f,sizeof(h));
for(int i=0,j=0;i<n;i++){
while(j<i && h[find(a[i])]!=null) h[find(a[j++])]=null;
if(h[find(a[i])]==null) h[find(a[i])]=a[i];
ans=max(ans,i-j+1);
}
printf("%d",ans);
}
int main(){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&a[i]);
//STL();
solve();
return 0;
}