算法1 滑动窗口

本来是用unordered_map来存窗口里的字符次数的，提交AC了但是发现时间1018ms太长，于是换成了数组来存，时间减少到了123ms~

时间复杂度O(n)

C++ 代码

#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
int main()
{
    int T;cin>>T;
    while(T--)
    {
        int res=300000;//答案一开始设为比题目数据范围大的值
        int tFreq[20];//存储123，用于和滑窗比较
        tFreq['1'-' ']=1;tFreq['2'-' ']=1;tFreq['3'-' ']=1;
        int winFreq[20];//存“滑动窗口”内字符出现次数
        memset(winFreq,0,sizeof(winFreq));//初始化
        string s;cin>>s;
        int n=s.size();
        bool p1=0;//用于判断是否有包含了1,2,3的子串
        int distance=0;//distance表示与目标“123”匹配的字符个数
        for(int i=0,j=0;j<n;j++)//j在右，i在左
        {
            winFreq[s[j]-' ']++;//先将当前位字符次数+1
            if(winFreq[s[j]-' ']<=tFreq[s[j]-' '])//如果滑窗内的字符次数小于等于tFreq对应字符的次数
            {
                distance++;//distance要增加1，表示匹配了1个字符
            }
            while(distance==3)//如果distance等于3进入缩小滑窗的循环(因为本题要匹配123，只有3个字符，每个一次)
            {

                if(winFreq[s[i]-' ']==tFreq[s[i]-' '])//如果滑窗内与tFreq共同存在的某个字符(1,2,3)次数相等
                {
                    distance--;//distance要减1，因为接下来i右移，把s[i]从滑窗去掉了，匹配的字符就减少了1
                }
                winFreq[s[i]-' ']--;//将s[i]在滑窗内的出现次数-1
                res=min(res,j-i+1);//更新滑窗长度最小值
                p1=1;//p1=1代表有满足条件的子串
                i++;//i右移1位，缩小滑窗
            }
        }
        if(p1==0) res=0;//没有满足条件的子串,res设为0
        cout<<res<<endl;
    }
    return 0;
}