题目翻译

有一个长度为 $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;
}