题目链接：http://codeforces.com/problemset/problem/701/C
题意： 给出一长度为n的字符串，问涵盖了所有在该串中出现过的字母的子串（连续）的最小长度是多少
分析： 从第一个字母开始，先找到包含所有字母的子串。想象该子串为一个队列，左边为队首，右边为队尾。左边的字母不断出队（如果出队后不会使某字母缺失），就可以更新最小长度。一旦无法出队，则右边的字母进队，然后继续判左边字母。
举个例子：给出一段序列，球区间和大等于10的最短区间。
序列： 2 5 8 7 3 2
①从头开始找到满足条件的区间， 2 5 8 7 3 2 –>最短长度为3 ②删除队首 2 ， 2 5 8 7 3 2 –>最短长度为2 ③删除队首5，无法删除，7进队， 2 5 8 7 3 2 –>最短长度仍为2 ④删除队首5， 2 5 8 7 3 2 –>最短长度为2 ⑤……以此类推
以上即为尺取法思想，复杂度O（n）
#include<cstdio> #include<iostream> #include<algorithm> #include<cmath> #include<queue> #include<cstring> #include<map> #include<vector> #include<set> using namespace std; #define Max(a,b) (a>b?a:b) #define Min(a,b) (a<b?a:b) #define INF ((1<<30)-1) #define in(x) scanf("%d", &x) #define inn(x,y) scanf("%d %d", &x,&y) #define lin(x) scanf("%I64d", &x) #define out(x) printf("%d\n", x) #define lout(x) printf("%I64d\n", x) #define rep(i,a,b) for(int i=a; i<=(b); i++) #define ll __int64 #define mem(a,b) memset(a, b, sizeof(a)) #define bug(x) cout<<#x<<" = "<<x<<"; " #define N 100005 #define M 1000000001 #define nn printf("\n") char s[N]; bool vis[500]; int last[500]; int main() { int n; in(n); scanf("%s", s+1); mem(vis,0); mem(last,0); int sum=0; rep(i,1,n) { if(vis[s[i]]==0) vis[s[i]]=1, sum++; } int l=1, r; for(r=1; r<=n; r++) { last[s[r]]=r; if(vis[s[r]]) vis[s[r]]=0, sum--; if(!sum) break; } int ans=r-l+1; while(r<=n) { last[s[r]]=r; while(last[s[l]]!=l) { l++; ans=Min(ans, r-l+1); } r++; } out(ans); return 0; }