小埋的优雅序列(据说也叫百万富翁的第二次实验QaQ)
题目描述
小埋最近迷上了优雅序列。
优雅序列的定义是,在一段连续的序列中,包含的数字中不会出现重复数字。
现在给你一个长度为 n 的数组,请你告诉小埋其中最长的优雅序列的长度是多少。
输入格式
第一行是一个正整数 n,n 表示数组的长度。
第二行有nn用空格隔开的正整数,有 n 个整数数字 i 。
输出格式
一个整数,符合题目要求的最长子数组的长度。
样例 #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;
暴力打法(50pts)
我们可以发现,这道题的暴力打法就是枚举 i ,当 i=1 时,优雅序列的中止在哪里,随后一直到 i=n 。
在枚举时,我们需要使用 map ,每到一个点就判断 map ,从而找到最长的序列。
核心代码:
int sum=1,ans=0;
for(int i=1;i<=n;i++){
mp[a[i]]=1;
for(int j=i+1;j<=n;j++){
if(mp[a[j]]==1) break;
mp[a[j]]=1;
sum++;
}
ans=max(ans,sum);
sum=1;
memset(mp,0,sizeof mp);
}
正解(100pts)
考虑双指针:将遍历的数->它的序列的结尾 随后调整序列的开头来使这个序列成为“优雅序列”。
每次遍历的数都要放入 map ,当遍历到 map 有的数时,调整开头,直到这个序列只包含一个这次遍历的数。
核心代码:
int l=1,r=2,ans=0;
mp[a[1]]=1;
while(r<=n){
if(mp[a[r]]==1){
for(;a[l]!=a[r];l++){
mp[a[l]]=0;
}
l++;
}
mp[a[r]]=1;
ans=max(ans,r-l+1);
r++;
}
(蒟蒻菜的要死,这题写了1小时)