n个数里,找到最长的一个连续序列使里面最多k个不同的数。
尺取法,每次R++,如果第R个数未出现过,那么不同的数+1,然后这个数的出现次数+1,如果不同的数大于k了,那就要去掉第L个数,直到不同的数为k,然后更新答案。
#include<cstdio>
#define ll long long
#define N 500005
int n,k;
int a[500005],num[1000005];
int l,r;
int s,ansl,ansr;
int main()
{
scanf("%d%d",&n,&k);
for(int i=1; i<=n; i++)
{
scanf("%d",&a[i]);
}
ansl=1;
ansr=k;
l=1;
r=0;
while(r<n)
{
r++;
if(num[a[r]]==0)s++;
num[a[r]]++;
while(s>k)
{
num[a[l]]--;
if(num[a[l]]==0)s--;
l++;
}
if(r-l>ansr-ansl)
{
ansr=r;
ansl=l;
}
}
printf("%d %d",ansl,ansr);
return 0;
}