题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

题目大意：

有

n

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

方法：

用

vector

存每个数的下标，便利

1

到

1e6

的所有数，如有出现多次的数，每次求两个相同数的下标的差，再将这些差求最小值。

AC code：

CPP

#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;	
}

题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

文章操作

题目大意：

方法：

相关推荐

评论

题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray