题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

· · 题解

比都比了，就写一发吧。

思路

双指针~~
这题很像双指针，所以用双指针
观察题目，可以发现：当一个以 l 为开头的有重复值的最短连续子序列的结尾为 r，则以 l+1 为开头的有重复值的最短连续子序列的结尾至少为 r。由此很容易看出此题可以用双指针。
我们从 1 至 n 枚举所有 l，对于每个 l，寻找以 l 为开头的有重复值的最短连续子序列的结尾 r，并将所有序列的长度取最小值输出。如果不存在以 l 为开头的有重复值的连续子序列，就不参与取最小值。
具体细节看代码吧！

代码

#include<bits/stdc++.h>
#define ll long long
#define pp pair<int,int>
using namespace std;
int n,ans,a[2000005],b[2000005];//b数组标记每个数是否出现过 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    cin>>n;
    ans=n+1;//ans设最大值 
    for(int i=1;i<=n;++i)cin>>a[i];
    for(int l=1,r=2;l<=n;++l){
        b[a[l]]=1;//标记a[l]这个数 
        while(!b[a[r]]&&r<=n||r<=l){
            b[a[r]]=1;//标记a[r] 
            ++r;
        }
        //寻找以l为开头的有重复值的最短连续子序列的结尾r
        if(b[a[r]])ans=min(r-l+1,ans);
        //如果存在以l为开头的有重复值的最短连续子序列，就取最小值 
        b[a[l]]=0;//去掉a[l]这个数 
    }
    if(ans==n+1)cout<<-1<<"\n";
    //如果不存在有重复值的连续子序列，输出-1 
    else cout<<ans<<"\n";
    return 0;
}