最小覆盖子串

这段代码实现了 LeetCode 第 76 题「最小覆盖子串」（Minimum Window Substring）的经典解法，采用 滑动窗口（Sliding Window） 算法，时间复杂度为 O(n)，空间复杂度为 O(1)（因为字符集大小有限，最多 128 个 ASCII 字符）。

/*

 * @lc app=leetcode.cn id=76 lang=cpp
 * @lcpr version=20004
 *
 * [76] 最小覆盖子串
 */


// @lcpr-template-start
using namespace std;
#include <algorithm>
#include <array>
#include <bitset>
#include <climits>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <queue>
#include <stack>
#include <tuple>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
// @lcpr-template-end
// @lc code=start
class Solution {
public:
    string minWindow(string s, string t) {
        //ADOBECODEBANC ABC
        unordered_map<char,int> need;
        unordered_map<char,int> windows;
        for(auto c:t)
        {
            need[c] ;
        }
        int left=0;
        int right=0;//左开右闭的区间
        int len=INT_MAX;
        int start=0;
        int valid=0;
        while(right<s.size())
        {
            char c=s[right];
            right ;
            if(need.count(c))
            {
                windows[c] ;
                if(need[c]==windows[c])
                {
                    valid ;
                }
            }
            while(need.size()==valid)//能进入这个循环，说明当前区间已经满足条件
            {
                if(right-left<len)
                {//更新长度
                    start=left;
                    len=right-left;
                }
                char d=s[left];
                left ;
                if(need.count(d))
                {
                    if(windows[d]==need[d])
                    {
                        valid--;
                    }
                    windows[d]--;
                }

            }
        }
        return len==INT_MAX?"":s.substr(start,len);
    }
};
// @lc code=end



/*
// @lcpr case=start
// "ADOBECODEBANC"\n"ABC"\n
// @lcpr case=end

// @lcpr case=start
// "a"\n"a"\n
// @lcpr case=end

// @lcpr case=start
// "a"\n"aa"\n
// @lcpr case=end

 */