独特的雪花

链接

这题需要我们寻找不重复的最长序列

比如一串序列

1 2 3 4 2 4 5 6 7

最长序列是1 2 3 4或4 5 6 7,也就是4

这题可以采用类似滑动窗口的方法(一次可能滑过多个元素,且不遍历)

用unordered_map记录每个元素的位置,为了方便我们从一开始

比如

1 2 3 4 5 1 2 1 4 6

未创建时,编号为0

创建时,编号为对应数字,也就是右窗口

#include<unordered_map>
#include<vector>
using namespace std;
#define ll long long
int main() {
	int n;
	cin >> n;
	while (n--) {
		ll T;
		cin >> T;
		vector<ll>num(T+1);
		unordered_map<ll,ll>se;
		for (ll i = 1;i <= T;i++) {
			cin >> num[i];
		}
		ll left = 1;
		ll  relen = 0;
		for (ll right = 1;right <= T;right++) {
			if (se[num[right]] < left||se[num[right]]==0) {//判定该元素不存在(即不在窗口内),我们更新元素位置
				se[num[right]] = right;
			}
			else if (se[num[right]] >= left) {//判定该元素已经存在,我们将左窗口跳转到旧元素位置加1并修正元素位置(此时旧元素不在窗口内)
				relen = max(relen, right - left);
				left = se[num[right]] + 1;
				se[num[right]] = right;//修正元素位置
			}
			if(right==T) relen = max(relen, right - left+1);//对最后一次进行处理
		}
		cout << relen << endl;
	}
}

时间复杂度:O(n)

空间复杂度:O(n)