leetCode 76. 最小覆盖子串 + 滑动窗口 + 哈希Hash

我的往期文章：此题的其他解法，感兴趣的话可以移步看一下：

leetCode 76. 最小覆盖子串 + 滑动窗口 + 图解（详细）-CSDN博客https://blog.csdn.net/weixin_41987016/article/details/134042115?spm=1001.2014.3001.5501
力扣题： 76. 最小覆盖子串 - 力扣（LeetCode）

关于 滑动窗口的相关知识点和此题的解题思路，可以看来自笨猪爆破组的这篇文章：76. 最小覆盖子串 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-window-substring/solutions/257928/yi-bu-bu-xing-cheng-hua-dong-chuang-kou-si-lu-shen/

本文就是参考该作者的解题思路做的 C++版本！Thanks♪(･ω･)ﾉ

C++ 代码： 

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int>need;
        int strStart=s.size(),windowLen=s.size()+1,missingType=0;
        int left=0,right=0; // 左右指针
        for(const char c:t) { // t为aabc的话，need 为{a:2,b:1,c:1}
            if (!need[c]) {
                missingType++; // 需要找齐的种类数 +1
                need[c]++;
            }else need[c]++;
        }
        while(right < s.size()) { // 主旋律扩张窗口，超出s串就结束
            char rightChar = s[right];
            if(need.find(rightChar)!=need.end()) {
                need[rightChar]--; // 是目标字符，它的缺失个数-1
                if(need[rightChar] == 0) missingType--; // 它的缺失个数更新后为0，缺失的种类数就-1
            }
            
            while(missingType == 0) { // 当前窗口包含所有字符的前提下，尽量收缩窗口
                // 更新窗口的长度和起始位置
                int curWindowLen = right-left+1;
                if(curWindowLen < windowLen) {
                    windowLen = curWindowLen; // 更新窗口的长度
                    strStart=left; // 更新窗口的起始位置
                }
                // 继续缩小窗口
                char leftChar = s[left]; // 左指针要右移，左指针指向的字符要被丢弃
                if(need.find(leftChar)!=need.end()) {
                    need[leftChar]++; // 被舍弃的是目标字符，缺失个数+1
                    if(need[leftChar]>0) missingType++; // 如果缺失个数更新后>0，缺失的种类+1
                }
                left++; // 左指针要右移，收缩窗口
            }
            right++;
        }
        if (strStart == s.size()) return "";
        return s.substr(strStart, windowLen); // 根据起点和windowLen截取子串
    }
};

推荐和参考文章：

76. 最小覆盖子串 - 力扣（LeetCode）https://leetcode.cn/problems/minimum-window-substring/solutions/257928/yi-bu-bu-xing-cheng-hua-dong-chuang-kou-si-lu-shen/