题目翻译
有一个长度为 $n$ 的序列 $a$,找出最长的 $[l,r]$ 使得 $a_l,a_{l+1},a_{l+2},\dots a_{r-1},a_r$ 不重复的数字个数 $\leq k$。
$1\leq k \leq n\leq 5\times 10^5,a_i\leq 10^6$
题目思路
分析一下复杂度,$n$ 的级别显然告诉我们要做到 $n^2$ 以下。
观察到固定左端点 $l$,随着 $r$ 往右推,不重复数字的个数也是单调不降的。考虑双指针。
我们先让 $r$ 往右挪动,每一步检查一下当前的不重复数字个数,如果不满足题意那么挪动左端点 $l$ 把不重复的数字个数控制在 $k$ 以内。
时间复杂度 $\mathcal O(n)$。
完整代码
代码
#include<bits/stdc++.h>
using namespace std;
int n,k;
int a[500020];
int cnt[1000020],sum;
int ansl=1,ansr;
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
int l=1,r=0;
while(r<n)
{
sum+=((++cnt[a[++r]])==1);
while(sum>k)sum-=(!(--cnt[a[l++]]));
if(r-l+1>ansr-ansl+1)ansr=r,ansl=l;
}
cout<<ansl<<" "<<ansr<<endl;
return 0;
}