算法|滑动窗口解法

窗口滑动算法

76. 最小覆盖子串 - 力扣（LeetCode）

class Solution {
public:
    string minWindow(string s, string t) {
        //初始化哈希表和对应的need表
        unordered_map<char,int> need,window;
        for(char c: t) need[c]++;
        //初始化各段标志数据
        int left = 0,right = 0;
        int valid = 0;
        int start = 0,len = INT_MAX;
        //下边进行扩大和缩减窗口
        while(right < s.size()){
            //扩大窗口
            char c = s[right];
            right++;
            //记录进对应的key中，符合该key，加一
            if(need.count(c)){
                window[c]++;
                if(window[c] == need[c]) valid++;
            }

            //减小窗口
            while(valid == need.size()){
                if(right-left < len){
                    //start记录边界值，left会比start多1，当left越过对应的边界，valid会减少，去除重复的后，循环结束
                    start = left;
                    len = right -left;
                }
                char d = s[left];
                left++;
                //key越界，就结束循环
                if(need.count(d)){
                    if(window[d] == need[d]) valid--;
                    window[d]--;
                }
            }
        }
        //判断返回
        return len == INT_MAX? "" : s.substr(start,len);
    }
};

本题使用到的是c++，其中的哈希表中，记录key是对应字符，value记录的是对应的字符个数，利用哈希表来对应查询