力扣精选算法100题——最小覆盖子串(滑动窗口专题）

本题链接——最小覆盖字串

---

第一步：了解题意

只要存在一段字符串中有t字符串的每个字符即可，返回的是最小长度包含t字符串各个字符。

但是有一个要注意：

s字符串中就一个字符，而t字符串中有2个a，所以是不能覆盖的，所以返回空串。

---

第二步：算法原理

🚩暴力枚举+哈希

这里是记录字符串每个字符的个数的，所以我们需要用hash来存。

我们这时候right又是往 回走。

我们来看看

同向移动这时候我们就想到了滑动窗口。其实我们应该更加了解的是why用滑动窗口，其次就是how用滑动窗口方法。

🚩滑动窗口+哈希

滑动窗口的模板：

1.left=0,right=0;

2.进窗口

3.判断

4.出窗口

更新结果（这是是在上面的4个步骤中根据题目的不同来穿插的）

2.进窗口
实际上，就是让right的值存入到hash表中（hash表其实就是一个一维数组）

3.判断

只要s字符串包含t字符串中所有字符即可。

4.出窗口
出窗口建立在判断的时候的 ，知道hash1表中的字符种类等于hash2中的有效字符种类，我们就得出窗口，left对应的值就得--，如果不等于hash1表中的字符种类那么就继续进窗口。

5.更新结果
结果是只要判断结果count==kinds就可以更新结果。

🎈优化：

用count来记录“有效字符”种类

A->1? ?A->1

B->2? ?B->1

C->3??C->1

因为我们不能重复的记录count

进窗口：进窗口后 当字符hash2[in]==hash1[in] count++

出窗口:? ?出窗口前 当字符hash2[out]==hash1[out] count--

判断条件： count==kinds(kinds指的是hash1中字符种类)

---

第三步：代码实现

class Solution {
public:
    string minWindow(string s, string t) {
        string ret;
        int hash1[128]={0};//统计字符串t中每个字符出现的次数
        int kinds=0;
        for(auto &ch:t){
            if(hash1[ch]++==0)kinds++;
        }//先入，再判断如果个数等于种类就++
        int hash2[128]={0};//统计字符串s中每个字符出现的次数
        int minlen=INT_MAX,begin=-1;
        for(int left=0,right=0,count=0;right<s.size();right++)
        {
            //进窗口+维护
            char in=s[right];
            if(++hash2[in]==hash1[in])count++;
            while(count==kinds)
            {
                if(right-left+1<minlen)///更新结果
                {
                    minlen=right-left+1;//长度
                    begin=left;//起始位置
                }
                //出窗口+维护count
                char out=s[left];
                if(hash2[out]--==hash1[out])count--;
                left++;
            }
        }
         if(begin==-1)return "";
        else return s.substr(begin,minlen);
    }
};

希望能尽快有经济基础吧。