“滑动窗口”和上篇博客中介绍的“等价转换”一样也为一种算法优化的思想。同样，下面通过一个例子，来介绍这种思想。
唯一的雪花（Unique snowflake，UVa 11572）
输入一个长度为n(n<=10^6)的序列A，找到一个尽量长的连续子序列AL~AR,使得该序列中没有相同的元素。
在读完题目以后，我们不难有思路。最简单的思路就是，我们可以通过循环的方法，对每一个元素都找出一它为开头的最长序列（没有相同元素）。这个方法也能做出来，但似乎有点太麻烦了。下面，我们就通过“滑动窗口”的思想来介绍这道题目的另一个思路。
【分析】
假设序列元素从0开始编号，所求连续子序列的左端点为L,又短点为R。首先，先考虑L=0的情况。可以从R=0不断增加R，相当于，把所求序列的右端点往右延伸。当R不能往右继续延伸时（即出现相同的元素时），只需将L不断增加至没有相同的元素时为止。然后再不断增加R，重复此步骤。
【代码】通过代码来实现上述过程，加深理解
#include<cstdio>
#include<set>
#include<algorithm>
using namespace std;
const int maxn=1000000+5;
int A[maxn];
int main()
{
int T,n;
scanf("%d",&T);
while(T--){
scanf("%d",&n);
for(int i=0;i<n;i++) scanf("%d",&A[i]);
set<int> s;
int L=0,R=0,ans=0;
while(R<n){
while(R<n&&!s.count(A[R])) s.insert(A[R++]);
ans=max(ans,R-L);
s.erase(A[L++]);
}
printf("%d\n",ans);
}
return 0;
}
同时，此题用C++的STL中的set，实现了这一过程。
免责声明：本站发布的内容（图片、视频和文字）以原创、转载和分享为主，文章观点不代表本网站立场，如果涉及侵权请联系站长邮箱：is@yisu.com进行举报，并提供相关证据，一经查实，将立刻删除涉嫌侵权内容。
