题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

liborui0000 · 2025-03-02 08:56:15 · 题解

题目大意：

有 n 个数，求一个最短子序列，使得这个子序列里有重复的元素。

方法：

用 vector 存每个数的下标，便利 1 到 1e6 的所有数，如有出现多次的数，每次求两个相同数的下标的差，再将这些差求最小值。

AC code：

#include <bits/stdc++.h>

using namespace std;

const int N = 2e5 + 10;

int n;
vector<int> g[1000010];

int main(){
    cin >> n;
    for (int i = 1; i <= n; ++i){
        int a;
        cin >> a;
        g[a].push_back(i);  
    }
    int minn = 0x3f3f3f3f;
    for (int i = 1; i <= 1e6; ++i){
        if (g[i].size() < 2) continue;
        for (int j = 1; j < g[i].size(); ++j)
            minn = min(g[i][j] - g[i][j - 1] + 1, minn);
    }
    if(minn == 0x3f3f3f3f) cout << -1;
    else cout << minn;
    return 0;   
}