题解 | #最小覆盖子串#

1. 典型的滑动窗口问题

class Solution {
public:
    /**
     * 
     * @param S string字符串 
     * @param T string字符串 
     * @return string字符串
     */
    string minWindow(string S, string T) {
        // write code here
        unordered_map<char,int> need, window;
        //首先，初始化 window 和 need 两个哈希表，记录窗口中的字符和需要凑齐的字符：
        for(char c:T){
            need[c]++;
        }
        //然后，使用 left 和 right 变量初始化窗口的两端，不要忘了，区间 [left, right) 是左闭右开的，所以初始情况下窗口没有包含任何元素：
        int left = 0,right = 0;
        int valid = 0;//其中 valid 变量表示窗口中满足 need 条件的字符个数，如果 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串 T。

        //开始滑动
        //记录最小覆盖子串的起始索引及长度
        int start = 0, len = INT_MAX;
        while(right<S.size()){
             // c 是将移入窗口的字符
            char c = S[right];
            // 右移窗口
            right++;
             // 进行窗口内数据的一系列更新
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]){
                    valid++;
                }
            }

            // 判断左侧窗口是否要收缩
            while(valid==need.size()){
                 // 在这里更新最小覆盖子串
                if(right-left<len){
                    start = left;
                    len = right - left;
                }
                //  d 是将移出窗口的字符
                char d = S[left];
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if(need.count(d)){
                    if(window[d] == need[d]){
                        valid--;
                    }

                    window[d]--;
                }


            }


        }


        return len == INT_MAX? "": S.substr(start,len);


    }
};