CodeForces 701C They Are Everywhere （滑动窗口）

小程序：扫一扫查出行
【扫一扫了解最新限行尾号】
复制小程序

题目链接：http://codeforces.com/problemset/problem/701/C

题意：找到字符串中能包含所有元素的最短字符串长度。

利用“滑动窗口”解题

解题思路：

1. 遍历找到所有元素进行统计，元素数sum

2.设置两个”指针“ st、en，双重while 循环

3.先清空dp[]数组，进行统计

双重while

第一个 whielt(st<n)

{

内部while(en<n&&sum!=sum1)//sum1统计元素个数

{//内部while

sum1 统计

dp[s[en]]++ 每个元素出现的次数统计

en++

}

如果sum==sum1 找到小值 ans=min(ans,en-st);

*如果--dp[s[st]]==0,则说明 s[st] 这个元素在统计的所有元素个数中没有了，此时sum1--,即应重新统计s[st] 这个元素,以确保长度包含所有元素。【关键点】

st++;

}

输出 asn 即可。

//16.09.07 22:10

看博再次看到滑动窗口，觉得解释的不算清晰，特补充解释下：

AC code:

#include<bits/stdc++.h>
using namespace std;
int dp[];
int main()
{
int n;
string s;
while(~scanf("%d",&n))
{
cin>>s;
int sum=;
memset(dp,,sizeof(dp));
for(int i=; i<n; i++)
{
if(!dp[s[i]])
{
dp[s[i]]=;
++sum;
}
}
int st,en,sum1,ans;
st=en=sum1=;
ans=<<;
memset(dp,,sizeof(dp));
while(st<n)
{
while(en<n&&sum!=sum1)
{
if(dp[s[en]]==)
{
sum1++;
}
dp[s[en++]]++;
}
if(sum==sum1)ans=min(ans,en-st);
if(--dp[s[st++]]==)sum1--;
}
cout<<ans<<endl;
}
return ;
}