专栏文章

题解：AT_abc395_c [ABC395C] Shortest Duplicate Subarray

LLovely_yhb
AT_abc395_c题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miq3f75r
此快照首次捕获于
2025/12/03 22:19
3 个月前
此快照最后确认于
2025/12/03 22:19
3 个月前
查看原文

题意

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

思路

发现值域非常小，Ai≤106A_i\le10^6。所以可以直接开桶。
开一个数组 pretpre_t，表示 tt 这个数上一次出现的位置。如果当前数字出现过，就统计答案。ans=min⁡(i−preai+1)ans=\min(i-pre_{a_i}+1)。

AC Code

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

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...