题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

Jerry_zpl · 2025-03-02 09:55:13 · 题解

这题很水。

问题陈述

给你一个正整数 N 和一个长度为 N 的整数序列 A。请判断 A 是否存在一个非空（连续）子数组，它有一个重复值，在 A 中出现多次。如果存在这样的子数组，求最短的子数组的长度。

思路：

• 我们可以定义一个数组 vis，用来标记 a_i 的位置。
• 当循环到 i 时，若 vis_{a_i}=1 则 a_i 之前出现过，符合题目中所说的数组，用变量 mini 求最短长度。
• 为啥 a_i 出现了两次就比较长度呢？因为题目让我们求最短的子数组的长度。所以出现了两次就符合条件了，没必要再看第三次出现的位置。
• 如果 vis_{a_i}=0，那么标记一下 a_i 出现的位置 i。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=1e6+5;
int a[maxn];
int vis[maxn];
signed main(){
    int n;
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    int mini=INT_MAX;
    for(int i=1;i<=n;i++){
        if(vis[a[i]]){
            mini=min(mini,i-vis[a[i]]+1);
        }
        vis[a[i]]=i;
    }
    if(mini==INT_MAX) mini=-1;
    cout<<mini<<"\n";
    return 0;
}