题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

Lovely_yhb · 2025-03-02 08:06:02 · 题解

题意

求出序列中相隔最近的两个相同数字的距离。

思路

发现值域非常小，A_i\le10^6。所以可以直接开桶。

开一个数组 pre_t，表示 t 这个数上一次出现的位置。如果当前数字出现过，就统计答案。ans=\min(i-pre_{a_i}+1)。

AC Code

#include<bits/stdc++.h>
using namespace std;
int lst[1000006],n,x,ans=0x3f3f3f3f;
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        if(lst[x]) ans=min(ans,i-lst[x]+1);
        lst[x]=i;
    }
    cout<<(ans==0x3f3f3f3f?-1:ans);
    return 0;
}