题目链接: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 ;
}