LeetCode 76. 最小覆盖子串

76. 最小覆盖子串

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

示例 2：

输入：s = "a", t = "a"
输出："a"

题解：滑动窗口

在这里插入图片描述
本题使用滑动窗口求解，即两个指针 l 和 r 都是从最左端向最右端移动，且 l 的位置一定在r 的左边或重合。注意本题虽然在 for 循环里出现了一个 while 循环，但是因为 while 循环负责移动 l 指针，且 l 只会从左到右移动一次，因此总时间复杂度仍然是 O(n)。本题使用了长度为 128 的数组来映射字符，也可以用哈希表替代；其中 chars 表示目前每个字符缺少的数量，flag 表示每个字符是否在 T 中存在

更多可参考官方题解：https://leetcode-cn.com/problems/minimum-window-substring/solution/tong-su-qie-xiang-xi-de-miao-shu-hua-dong-chuang-k/

代码

class Solution { 
public:
    string minWindow(string s, string t) { 
        // 一共就128个字符 chars记录每个字符的数量，flag记录是否存在这个字符
        vector<int> chars(128,0);
        vector<bool> flag(128,false);
        // 先统计T中拥有的字符情况
        for(int i=0;i<t.size();i++)
        { 
            chars[t[i]]++;
            flag[t[i]]=true;
        }
        int count=0,l=0,min_l=0,min_size=s.size()+1;
        for(int r=0;r<s.size();r++)
        { 
            // 如果当前遍历到的字符在t中存在
            if(flag[s[r]])
            {        
                if(--chars[s[r]]>=0)
                { 
                    count++; 
                }
                // 如果当前滑动窗口包含了 t 中所有的字符，那么尝试将 l 向左移，在不影响满足条件的情况下获得最短情况
                while(count==t.size())
                { 
                    // 如果当前包含了所有的 t中字符，并且长度小于当前最小，那么重新赋值
                    if(r-l+1<min_size)
                    { 
                        min_size=r-l+1;
                        min_l=l;
                    }
                    if(flag[s[l]]&&++chars[s[l]]>0)
                    { 
                        count--;
                    }
                    l++;    // l 右移动（不需要担心破坏满足条件，因为上面的判断已经保存了最小的）
                }
             }
        }
        return min_size>s.size()?"":s.substr(min_l,min_size);
    }
};