本题的思路承接题解4,额外加入了对字符串知识的一些考察。

时间超限的思路:一开始我想着题解4用sum是否大于goalsum来判断是否达到题目要求,那么这道题是不是可以创建一个函数,接收一个字符串,来判断是否达到题目要求,我去尝试了,代码如下(时间超限)。

#include<iostream>
#include<string>
using namespace std;
bool has_all_string(string &str)
{   
    if(str.size()<26){return false;}
    int t[26]={0};
    for(int i=0;str[i]!='\0';i++)
    {
        int div=str[i]-'a';
        t[div]=1;
    }
    for(int i=0;i<26;i++){if(t[i]==0){return false;}}
    return true;
}
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    string str;cin>>str;
    int len=str.size();//str.length()
    int r=0;string temp;int minlen=len+1;
    for(int i=0;i<len;i++)
    {
        while(r<len && !has_all_string(temp))
        {temp+=str[r];r++;}
        //cout<<"i="<<i<<' '<<"r="<<r<<' '<<endl;
        if(has_all_string(temp))
        {   
            minlen=min(minlen,r-i);
        }
        else {break;}
        temp.erase(0,1);
    }
    if(minlen==len+1){cout<<-1;}
    else {cout<<minlen;}
}

为什么时间会超限?看似用上了双指针减少时间复杂度,但内层循环某一次都在调用has_all_string函数,我们设想一个字符串 a*90000+bcdefghijklmnopqrstuvwxyz,那么到它第一次找到符合要求的字符串,调用了100000次函数。而且越到后面传入的str就越大,在has_all_string内部中的循环次数也越多。如同认为嵌套了一次循环。

怎么办?那只有不调用函数,当前字符串是否符合题目要求的判断要在双指针循环体中完成。最重要的是,不能每次在字符串多加一个字符,就要重新判断这个新的字符串是否符合题意,我们要让前面已经进行的判断有效阿。!

if(person==me)
{
    想想(/*for*/a 很长的 time);//long是关键字
}

很好,那就新建一个数组,用来判断当前字符串每个字符的出现次数,因为即使你仅仅把某个子串中字符的顺序调换(不考虑顺序),完全不影响它是否是最短合法子串。这样,每次对当前字符串末尾添加一个字符(即右界右移一次),只需简单的修改下这个26个元素的数组(初始化全为0)。字符串中的某个字符-'a'即是他的(索引)下标。好了,记录字符出现次数的数组有了,那么如何判断是否找全了26个小写字母呢?用一个count变量,如果右界上的那个字符之前从未出现过(对应数组的元素为0),那么count++,然后让对应的数组元素++(为了后面左界右移删去字符做准备)。知道符合题目要求前右移右界。如果右界移到尽头了,还是不符合条件就break;如果符合条件了就记录下当时的串长度。把左界上的字符对应的数组元素减1,如果减没了,count--,然后通过for中的i++右移左界......

AC代码:

#include<iostream>
#include<string>
using namespace std;
int a[26]={0};
int main()
{
    ios::sync_with_stdio(false);cin.tie(nullptr);
    string str;cin>>str;
    int len=str.size();
    int cnt=0;int minlen=len+1;
    for (int i=0,j=0; i<len; i++) 
    {
        while(j<len && cnt<26)
        {
            if(a[str[j]-'a']==0){cnt++;}
            a[str[j]-'a']++;
            j++;
        }
        if(cnt==26)
        {    
            minlen=min(minlen,j-i);//因为最后多了一次j++,故这里为[(j-1)-i]+1=j-i
            a[str[i]-'a']--;
            if(a[str[i]-'a']==0){cnt--;}
        }
        else {break;}
    }
    if(minlen!=len+1){cout<<minlen;}//注意minlen不要打成len了
    else {cout<<-1;}
    
    return 0;
}