【C++习题】16.滑动窗口_最小覆盖子串

文章目录

• • 题目链接：
  • 题目描述：
  • 解法
  • C++ 算法代码：
  • 图解

题目链接：

76. 最小覆盖子串

题目描述：

解法

暴力解法：

列出所有符合要求的字串，然后比较大小。

滑动窗口+哈希表

比如，如果已经符合要求了

那么left右移一位的话，right需要移动吗？

1. left指向的地方恰好有符合t的字符，->right不动
2. left指向的地方恰好没有符合t的字符，->right动

解法：

1. left=0，right=0

2. 进窗口：hash2[in]++

3. 判断：check(hash1,hash2)

   更新结果：起始位置，最短长度

   决定是否出窗口：hash2(out)--

我们可以优化一下：

使用count来标记有效字符的种类。

之前标记的是有效字符的次数，这边是种类，因为如果是次数的话，t里面是ABC，1+1+1=3，s里面是BBC，那么2+1=3，是无法解决这个问题的。

1. 进窗口：进去之后，当hash2(in)==hash1(in);count++
2. 出窗口：出之前，当hash2(out)==hash1(out);count--
3. 判断条件：count==hash1.size()

C++ 算法代码：

class Solution 
{
    public:
    string minWindow(string s, string t) 
    {
        int hash1[128] = { 0 }; // 初始化一个大小为 128 的整型数组 hash1，并将所有元素初始化为 0
        int kinds = 0; // 统计有效字符有多少种
        for(auto ch : t){ // 遍历字符串t，统计每个字符的频次，并计算不同字符的种类数
            if(hash1[ch]++ == 0) 
            {
                kinds++;
            }
        }
        int hash2[128] = { 0 }; // 统计窗口内每个字符的频次
        int minlen = INT_MAX, begin = -1; // 记录最小窗口的长度，初始化为最大值，记录最小窗口的起始位置，初始化为-1
        for(int left = 0, right = 0, count = 0; right < s.size(); right++)
        {
            char in = s[right];// 当前进入窗口的字符
            if(++hash2[in] == hash1[in]) // 更新hash2中该字符的频次
            {
                count++; // 进窗口 + 维护 count
            }
            while(count == kinds) // 当count等于kinds时，说明当前窗口包含t中所有字符
            {
                if(right - left + 1 < minlen) // 更新最小窗口的长度和起始位置
                {
                    minlen = right - left + 1;
                    begin = left;
                }
                char out = s[left++]; // 尝试缩小窗口，移除最左边的字符
                if(hash2[out]-- == hash1[out]) 
                {
                    count--; // 出窗口 + 维护 count
                }
            }
        }
        if(begin == -1) // 如果begin没有被更新，说明不存在包含t的窗口，返回空字符串
        {
            return "";
        }
        else
        {
            return s.substr(begin, minlen);// 否则，返回从begin开始的最小窗口子串
        }
    }
};

图解

例如：s = "ADOBECODEBANC", t = "ABC"

1. hash1[A]=1，hash1[B]=1，hash1[C]=1，kind=3

   left = 0, right = 0, count = 0，进入循环

   in=A，++hash2[in]=2，hash1[in]=2，count++，count=1

   right++

2. left = 0, right = 1, count = 1，进入循环

   in=D，++hash2[in]=2，hash1[in]=1，count=1

   right++

3. left = 0, right = 2, count = 1，进入循环

   in=O，++hash2[in]=2，hash1[in]=1，count=1

   right++

4. left = 0, right = 3, count = 1，进入循环

   in=B，++hash2[in]=2，hash1[in]=2，count++，count=2

   right++

5. left = 0, right = 4, count = 2，进入循环

   in=E，++hash2[in]=2，hash1[in]=1，count=2

   right++

6. left = 0, right = 5, count = 2，进入循环

   in=C，++hash2[in]=2，hash1[in]=2，count++，count=3

   count == kinds，进入while循环

   right - left + 1 < minlen，进入if

   minlen = right - left + 1; minlen=5-0+1=6
begin = left; begin=0

   char out = s[left++]; out=s[0]=A，left=1

   hash2[out]-- == hash1[out] == 3

   count--; count=2

   right++

7. left = 1, right = 6, count = 2，进入循环

   后面的过程一样，就不多赘述了。