【优选算法必刷100题】第016题（同向双指针：滑动窗口算法）：最小覆盖子串

艾莉丝努力练剑

发布于 2025-11-16 20:33:05

1030

文章被收录于专栏：C / C++C / C++

016 串联所有单词的子串

力扣链接（任选一个链接做就可以了，博主写的是76题，推荐先做76题）：

76. 最小覆盖子串 LCR 017. 最小覆盖子串

力扣题解链接（两个题目是非常相似的，博主就只挂76题的题解链接了）：

滑动窗口 + 哈希表解决【最小覆盖子串】

题目描述：

两道题是非常相似的，所以大家任选一个链接点过去做就可以了。这里博主介绍的是76题。

1.1 算法思路——滑动窗口 + 哈希表

算法思路：研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。

如何判断当前窗口内的所有字符是符合要求的呢？

（1）我们可以使用两个哈希表，其中一个将目标串的信息统计起来，另一个哈希表动态的维护窗口内字符串的信息。（2）当动态哈希表中包含目标串中所有的字符，并且对应的个数都不小于目标串的哈希表中各个字符的个数，那么当前的窗口就是一种可行的方案。

1.2 算法流程

1、定义两个全局的哈希表：号哈希表hash1用来记录子串的信息，2号哈希表hash2用来记录目标串t的信息；

2、实现一个接口函数，判断当前窗口是否满足要求——

（1）遍历两个哈希表中对应位置的元素：

1) 如果中某个字符的数量大于窗口中字符的数量，也就是2号哈希表某个位置大于号哈希表。说明不匹配，返回false； 2) 如果全都匹配，返回true。

1.3 主函数

1、先将的信息放入2号哈希表中； 2、初始化一些变量：左右指针：left = 0，right = 0；目标子串的长度：len = INT_MAX；目标子串的起始位置：retleft；(通过目标子串的起始位置和长度，我们就能找到结果） 3、当right小于字符串s的长度时，一直下列循环—— （1）将当前遍历到的元素扔进1号哈希表中；（2）检测当前窗口是否满足条件——

如果满足条件： 1）判断当前窗口是否变小。如果变小：更新长度len，以及字符串的起始位置 retleft； 2）判断完毕后，将左侧元素滑出窗口，顺便更新号哈希表； 3）重复上面两个过程，直到窗口不满足条件；

4、判断len的长度是否等于INT_MAX——

（1）如果相等，说明没有匹配，返回空串；（2）如果不想等，说明匹配，返回s中从retleft位置往后len长度的字符串。

1.4 算法实现

class Solution {
public:
    string minWindow(string s, string t) {
        //用数组模拟哈希表，特点：快
        int hash1[128] = {0};// 统计字符串t中每一个字符的频次
        int kinds = 0;// 用kinds统计有效字符的种类
        for(auto ch : t)
            // if(hash1[ch] == 0) kinds++;
            // hash1[ch]++;
            // //同理，这里也可以合并
            if(hash1[ch]++ == 0) kinds++;// 加之前判断，所以可以这样写
        int hash2[128] = {0};// 统计窗口内每个字符的频次

        int minlen = INT_MAX,begin = -1;// 一开始是-1，最大是INT_MAX
        for(int left = 0,right = 0,count = 0;right < s.size();right++)
        {
            char in = s[right];
            // hash2[in]++;
            // if(hash2[in] == hash1[in]) count++;// 有效字符
            // // 可以合并成一句
            if(++hash2[in] == hash1[in]) count++; //进窗口 + 维护 count
            //判断条件
            while(count == kinds)// 窗口大小不是固定的，这里不能用if
            {
                if(right - left + 1 < minlen)// 更新结果
                {
                    minlen = right - left + 1;// 更新最短长度
                    begin = left;// 更新起始位置
                }
                char out = s[left++];
                //出窗口之前要判断一下，维护count
                // if(hash2[out] == hash1[out]) count--;// 有效字符种类会减少
                // hash2[out]--;
                //因为这里先判断，再使用，可以合并
                if(hash2[out]-- == hash1[out]) count--;
            }
        }
        //有可能不存在起始位置，应该判断一下
        if(begin == -1) return "";
        else return s.substr(begin,minlen);
    }
};