Leetcode|滑动窗口|76. 最小覆盖子串

1 滑动窗口

代码语言：javascript复制

class Solution {
public:
    string minWindow(string s, string t) {
        // need表示t对应的<字符, 频率>，window表示s的
        unordered_map<char, int> need, window;
        // 先根据已知计算得到t对应的每个字符频率
        for (auto& c : t) need[c]  ;
        // start表最小子串起始索引, len表示长度，用于调用substr
        int start = 0, len = INT_MAX;
        // [left, right), vaild表示合法字符个数，对于t="ABC",需要vaild=3方可说明子串包含t
        int left = 0, right = 0, vaild = 0;
        // 1.窗口右侧增大
        while (right < s.size()) {
            char in = s[right];
            right  ;
            // 若从右边新增的in是need字符，判断是否满足单个字符合法性
            if (need.count(in)) {
                window[in]  ;
                if (window[in] == need[in]) vaild  ;
            }
            // 2.窗口左侧缩小 (当窗口内子串包含t)
            while (vaild == need.size()) {
                if (right - left < len) {
                    len = right - left;
                    start = left;
                }
                char out = s[left];
                left  ;
                // 若从左侧移除的元素out是原window对应t中字符，则需判断是否还合法，并更新window字符频率
                if (window.count(out)) {
                    if (window[out] == need[out]) vaild--;
                    window[out]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

leetcode

0 人点赞