Link: Dominated Subarray

C. Dominated Subarray

Description:
Let's call an array t dominated by value v in the next situation.

At first, array t should have at least 2 elements. Now, let's calculate number of occurrences of each number num in t and define it as occ(num). Then t is dominated (by v) if (and only if) occ(v)>occ(v′) for any other number v′. For example, arrays [1,2,3,4,5,2], [11,11] and [3,2,3,2,3] are dominated (by 2, 11 and 3 respectevitely) but arrays [3], [1,2] and [3,3,2,2,1] are not.

Small remark: since any array can be dominated only by one number, we can not specify this number and just say that array is either dominated or not.

You are given array a1,a2,…,an. Calculate its shortest dominated subarray or say that there are no such subarrays.

The subarray of a is a contiguous part of the array a, i. e. the array ai,ai+1,…,aj for some 1≤i≤j≤n.

Input
The first line contains single integer T (1≤T≤1000) — the number of test cases. Each test case consists of two lines.

The first line contains single integer n (1≤n≤2⋅1e5) — the length of the array a.

The second line contains n integers a1,a2,…,an (1≤ai≤n) — the corresponding values of the array a.

It's guaranteed that the total length of all arrays in one test doesn't exceed 2⋅1e5.

Output
Print T integers — one per test case. For each test case print the only integer — the length of the shortest dominated subarray, or −1 if there are no such subarrays.

Example
input
4
1
1
6
1 2 3 4 5 1
9
4 1 2 4 5 4 3 2 1
4
3 3 3 3
output
-1
6
3
2
Note
In the first test case, there are no subarrays of length at least 2, so the answer is −1.

In the second test case, the whole array is dominated (by 1) and it's the only dominated subarray.

In the third test case, the subarray a4,a5,a6 is the shortest dominated subarray.

In the fourth test case, all subarrays of length more than one are dominated.

Problem solving:
这道题的意思就是给你一个数列，让你找到两个相等的数(要求他们中间没有出现别的相等的数)之间的距离。

直接用一个数组记录一下某个数的出现位置。如果输入的时候发现这个数出现过，更新一下min的答案值以及这个数最新出现的位置。一开始我在纠结这样找会忽略两个数中间出现另外相等的数的情况，但是仔细一想我们让求得是最小值，如果两个数中间出现了另外两个相等的数，早就被min更新到ans了。题不难，主要是思想。所以还是记录一下。

Code:

#include <bits/stdc++.h>
using namespace std;
int main()
{
    int t, n;
    cin >> t;
    while (t--)
    {
        int         ans = 0x3f3f3f3f;
        cin >> n;
        vector<int> a(n +1); vector<int> pos(n+1);
        for (int i = 1; i <= n; i++)
        {
            cin >> a[i];
            if (!pos[a[i]])
                pos[a[i]] = i;
            else
                ans = min(ans, i - pos[a[i]]+1), pos[a[i]] = i;
        }
        if (ans == 0x3f3f3f3f)
            cout << "-1\n";
        else
            cout << ans << endl;
    }
}
赏