题目大意:给你个全部小写英文字母的字符串,问你子串中包含26个英文小写字母的最短子串是多少
思路:直接尺取法,一开始右指针一直往右移动直到子串符合要求,符合要求后左指针再向右移动以去掉重复字母得到子串的长度,之后再重复流程,利用一个变量储存最小长度即可
代码如下:
#include <iostream> #include <string.h> #include <cstdio> #include <map> using namespace std; char s[1000010]; int c[26]= {0};//记录每个小写字母的出现次数 int main() { cin>>s; int cnt=0;//记录出现了多少种英文字母的变量 int ans=10000000; int n=0; int i=0;//i为左边界,n为右边界 int len=strlen(s); // cout<<'z'-'a'<<endl; while(i<len) { while(n<len&&cnt<26)//防止n越界 { if(c[s[n]-'a']==0) cnt++; c[s[n++]-'a']++; } if(n-i<ans&&cnt==26)ans=n-i; if(c[s[i]-'a']==1) cnt--; c[s[i++]-'a']--; } cout<<ans; return 0; }