LeetCode_C++滑动窗口算法——最小覆盖子串_leetcode 最小覆盖子串 c++

1.最小覆盖子串

思路

1. 对于字符串s来讲，初始化左右指针left，right=0
2. 左右指针区间为[left，right)，这个区间称为一个窗口
3. 不断增加right，使窗口增大，直到窗口的字符串包含了T字符串的所有字符
4. 停止增加right，增加left，减小窗口，直到窗口的字符串不符合要求
5. 重复执行3，4步
6. 停止循环的条件为right到大字符串s的末尾（为了找到最小值）

初始化两个哈希表window，need记录窗口的字符以及所需要凑齐的字符，再定义变量valid表示窗口中满足need条件的个数，如果valid==need.size()，说明符合情况

C++实现

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int>window;
        unordered_map<char,int>need;
        int left=0;int right=0;
        int valid=0;
        int start=0;int len=INT_MAX;//记录子串的起始位置与长度
        for(auto ch:t)
        {
            need[ch]++;
        }
        while(right<s.size())
        {
            char c=s[right];//因为是[left,right)，所c是将要进入窗口的字符
            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;
                }
                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);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48