蓝桥杯备考：滑动窗口（双指针）算法之唯一的雪花

唯一的雪花 Unique Snowflakes - 洛谷 | 计算机科学教育新生态

如果两个指针不回退，我们就可以用滑动窗口来做，分析一下题目可以知道 我们就是在这几个数里找出最长的连续的没有重复数字的子数组的长度

我们的解法一就是所谓的暴力枚举，

以第一个元素开头找出最长的连续子数组，先固定第一个元素，然后从第一个元素开始往后遍历，找到没有重复数字的子数组，记录长度，接下来固定第二个，时间复杂度实际上是O(N²）的

但是实际上呢？我们是可以用双指针进行优化的

如图固定第一个元素的时候最长就是到这里了，如果是暴力枚举的话我们会把left变到2那里，然后让right也回去，但是实际上呢，right是可以不回退的，因为在right原地不动的状态下，left右移是不可能有比上一个更长的子数组的，然后我们的3会干扰1到3这个区间，left不管是在1还是2还是3，到right指的那个3，都会停止，所以我们应该把这个干扰项排除出去，也就是说，如果left到right的区间不合法，就让left一直++把干扰项排出去，right不动，如果left和right合法的话就让right一直++ 不断更新结果

我们的滑动窗口最长的时候就是left和right都把数组走完，这样我们的时间复杂度就是O（N），比之前快了很多

那么！怎么用滑动窗口呢

第一步是初始化 left = 1,right = 1,用unordered_map<int,int>维护窗口

第二步是进窗口，怎么进呢？让right所指的元素进窗口就行了，也就是 mp[a[right]]++

第三步是判断和出窗口，如果mp[a[right]]>1，这段区间就不合法了，要从left端开始出窗口，不断的让mp[a[left]]-- 然后让left++，直到mp[a[right]]是1的时候结束出窗口

第四步是更新结果 也就是让每个合法区域和最长的子数组长度作比较来更新长度

说了这么多，我们来写一下代码吧

#include <iostream>
#include <unordered_map>
using namespace std;
const int N = 1e6 + 10;
int a[N];
int main()
{
	int T; cin >> T;
	while (T--)
	{
		int ret = 0;
		unordered_map <int, int> mp;
		int n; cin >> n;
		for (int i = 1; i <= n; i++) cin >> a[i];
		int left = 1, right = 1;
		while (right <= n)
		{
			//进窗口 
			mp[a[right]]++;
			while (mp[a[right]] > 1)
			{
				mp[a[left]]--;
				left++;
			}
			ret = max(ret, right - left + 1);
			right++;
		}
		cout << ret << endl;
	}



	return 0;
}