题目描述
小埋最近迷上了优雅序列。
优雅序列的定义是,在一段连续的序列中,包含的数字中不会出现重复数字。
现在给你一个长度为 n 的数组,请你告诉小埋其中最长的优雅序列的长度是多少。
输入格式
第一行是一个正整数 n , n 表示数组的长度。
第二行有 n 用空格隔开的正整数,有 n 个整数数字ii。
输出格式
一个整数,符合题目要求的最长子数组的长度。
样例 #1
样例输入 #1
5
1 2 3 1 2
样例输出 #1
3
样例 #2
样例输入 #2
9
1 1 1 2 2 2 1 1 3
样例输出 #2
2
提示
1<=n<=2*10^5
1<=i<=2*10^5
这题得用双指针:
int get(int a[],int n){
int st=0,mlen=0,en=0;
unordered_set<int> s;
for(int i=0;i<n;i++){
while(s.find(a[i])!=s.end()){
s.erase(a[st]);
st++;
}
s.insert(a[i]);
if(i-st+1>mlen){
mlen=i-st+1;
en=i;
}
}
return mlen;
}
//核心函数如上
在这个代码中,我们使用了两个指针st
和en
来表示滑动窗口的起始和结束位置。我们还使用了一个unordered_set
来存储窗口中的字符,以便在O(1)时间复杂度内检查字符是否已经出现过。