题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

这题很水。

问题陈述

给你一个正整数

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$ 。

CPP

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

题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

文章操作

问题陈述

思路：

相关推荐

评论

题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray