算法题（135）：唯一的雪花

审题：

本题需要我们对于每一组数据都找出最大的包裹大小

思路：

本题解析题目意思后我们可以把雪花的编号当成数组中元素的值，把包裹看成一个区间。

本质上就是让我们找出一组数据中，所有子段中最长的子段。

方法一：暴力解法

我们利用双层for循环遍历每一个子段，然后利用unordered_map来记录子段区间的对应编号出现次数

不过这样的话，由于内层的索引每次都要回到和外层索引一样的位置，内层循环的遍历次数就会比较多

方法二：滑动窗口（优化暴力解法）

简单来说就是一种指针不回退的搜索方法

当我们搜索到一个编号的雪花出现了两次的时候，我们就需要记录区间长度，然后将区间范围缩小，也就是left--。

此时我们的left可以移动到两个区域

第一个是非法区域：也就是仍然有出现了两次的编号在区间范围内的区域

第二个是合法区域：也就是出现了两次的编号已经有一个离开区间了的区域

若是非法区域，就算按照暴力解法将right回退也无法找到比当前更长的区间，所以没有必要回退

若是合法区域，即使回退了也还是要指回当前right的索引位置，所以也没有必要回退。

得出结论：无论如何right都不用回退

接下来我们看看滑动过程：

（1）初始状态

（2）滑动

当区间中仍然存在出现两次的编号，就不断left--缩短区间（此时不用记录长度，因为一定没有之前没缩短区间的时候长），直到合法为止，合法后即可记录区间长度，然后right++继续往后滑动。

解题：
 

#include<iostream>
#include<algorithm>
#include<unordered_map>
using namespace std;
const int N = 1e6 + 10;
unordered_map<int, int> m;
int t, n;
int a[N];
int maxsize;
int main()
{cin >> t;while (t--){//清空上一组残留数据maxsize = 0;m.clear();//数据录入cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}//开始搜索int left = 1;for(int right = 1; right <= n; right++){++m[a[right]];while(m[a[right]] > 1)//继续缩短区间{m[a[left]]--;left++;}maxsize = max(maxsize, right - left + 1);}cout << maxsize << endl;}return 0;
}

1.数组a是不用重置的，因为我们每一组数据都会重新录入，且只访问到n，不会访问到残留数据

2.unordered_map和unordered_set的清空都是使用clear

3.由于right索引位置也是属于区间内的（区间左闭右闭），所以我们进行size计算的时候需要再加个1

UVA11572 唯一的雪花 Unique Snowflakes - 洛谷