11572_page-0001.jpg

 

给定一个数组，求数组中最长连续无重复元素的区间的长度。

滑动窗口。

先预处理处每个位置与该位置上数字相等的在该位置左边的最近的下标。

L和R从0开始，若R+1所在位置上数字最近的重复元素不在当前区间内，则R++，否则L跳到该重复元素所在位置+1，R++。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 10;
int t, n;
int a[maxn];
map<int, int>mp;
int pos[maxn];
int main() {
	scanf("%d", &t);
	while (t--) {
		mp.clear();
		scanf("%d", &n);
		for (int i = 0; i < n; i++) {
			scanf("%d", &a[i]);
		}
		for (int i = 0; i < n; i++) {
			if (!mp.count(a[i])) {
				mp[a[i]] = i;
				pos[i] = -1;
			}
			else {
				pos[i] = mp[a[i]];
				mp[a[i]] = i;
			}
		}
		int L = 0, R = 0;
		int ans = 1;
		while (R < n - 1) {
			if (pos[R + 1] < L) {
				R++;
				ans = max(ans, R - L + 1);
			}
			else {
				R++;
				L = pos[R] + 1;
			}
		}
		cout << ans << endl;
	}
	return 0;
}