leetcode 第 76 题：最小覆盖子串(C++)

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

和这个：LeetCode第 3 题：无重复字符的最长子串(C++)_qq_32523711的博客-CSDN博客有点相似

如果使用暴力解法：

for (int i = 0; i < s.size(); i++) 
    for (int j = i + 1; j < s.size(); j++)  
    	//i, j相当于窗口左右边界
        if s[i:j] 完全覆盖 t
            更新窗口长度（并记录边界）

至少是O(n^2)的时间复杂度（其实还需要对覆盖与否进行判断等等）

这种类型题目一般是用双指针法（滑动窗口）

对了，下面这个测试样本好坑，意味着不能使用set了

输入：
"aa"
"aa"
预期结果:
"aa"

参考位哥们的题解蛮有意思，说的简单易懂，思路很清晰：

把滑动窗口算法变成了默写题 - 力扣（LeetCode）

滑动窗口的算法逻辑一般为：

int left = 0, right = 0; // 初始化左右边界

while (right < s.size()) {`
    // 增大窗口
    window.add(s[right]);
    right++; //移动右边界
    
    while (符合要求) {
        // 缩小窗口
        window.remove(s[left]);
        left++; //移动左边界
    }
}

大致框架：

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
	//不一定是这两个数据结构
    unordered_map<char, int> need, window; //计数器用于判断窗口是否符合要求
    for (char c : t) need[c]++;
    
    int left = 0, right = 0; //初始化左右边界

    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据更新

        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据更新
            ...
        }
    }
}

滑动窗口算法思路：

1、字符串 S 中使用左右指针，初始化 left = right = 0，左闭右开区间 [left, right) 称为一个「窗口」

2、先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含 T 中的所有字符）

3、此时，停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不再包含 T 中所有字符）。同时，每次增加 left，都要更新一轮结果（窗口长度）。

4、重复第 2 、 3 步，直到 right 到达字符串 S 的尽头。

第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。

class Solution {
public:
    string minWindow(string s, string t) {
        // window为窗口中的字符，need为需要凑齐的字符
        unordered_map<char, int> need, window;
        for(const auto &c : t)  ++need[c];
        int left = 0, right = 0; //初始化左右边界，左闭右开
        //每当need中有一个字符查全，count就加一
        //当count==need.size()时代表找到一个符合要求的窗口
        int count = 0; 
        int start = 0, len = INT_MAX; //分别记录最小左边界和最小窗口长度
        while(right < s.size()){
            auto c = s[right]; //字符c即将进入窗口
            ++right; // 右移窗口
            //字符进入窗口
            if(need.count(c)){//如果字符c是t中的字符
                ++window[c]; //增加计数器
                if(window[c] == need[c]) //字符c已查全
                    ++count;
            }
            //判断左侧边界是否需要收缩，注意是while循环
            while(count == need.size()){ //窗口里所有字符的个数均达到要求
                //更新子串长度
                if(right - left < len){
                    start = left; //记录最小时候的窗口左边界（后面需要输出子串）
                    len = right - left;
                }
                //字符d即将移出窗口
                auto d = s[left];
                left++; //左移窗口
                // 进行窗口内数据的一系列更新
                if(need.count(d)){ //如果刚才移出的字符刚好也是t里面的字符
                    if(window[d] == need[d])
                        --count;
                    --window[d];
                }//否则就继续增加左边界，直到窗口window的数据不再满足要求（count != need.size()）
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

补充说明： if(need.count ( c )) 是一种 C++ 中 map 数据结构的使用方法。

map 是一种关联式容器，其中的元素是通过键值对（key-value）来存储和访问的。在 map
中，每个键（key）都唯一对应一个值（value），因此可以通过键来快速查找对应的值。

在这里，need 可以看作是一个存储目标字符串中指定字符的出现次数的 map，其中 key 为目标字符串中出现的字符，value
为该字符在目标字符串中出现的次数。need.count© 的作用是判断在 map need 中是否已经存在字符 c，如果存在则返回
1，否则返回 0。这里的返回值可以用于条件判断，例如：

    // 如果 c 存在于 need 中
    // ... } else {
    // 如果 c 不存在于 need 中
    // ... } ```

更一般地，count() 函数可以用于判断 map 中是否存在某个键值对。如果存在，返回值为 1，否则返回值为
0。在实际使用中，count() 函数常常被用来判断 map 中是否存在某个键，以免出现访问不存在键值对的情况。

代码逻辑确实很清晰，我自己写的时候也是这么考虑，但是逻辑确实没这么条理清晰。

最后可以看这儿：leetcode 第 567 题：字符串的排列(C++)_qq_32523711的博客-CSDN博客

其实很多时候哈希表可以修改为数组，两个哈希表也可以用一个哈希表解决（一边增一边减，看最后是否为0），甚至一个数组。因为我们使用这些容器的目的只是为了计数，能够准确设计好计数细节，用什么容器都可以。

只使用一个哈希表，思路就是t用于增加计数，s中的子串用于减小计数，当计数为0的时候不就是对应字符查全的时候吗？：

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need;
        for(auto c : t) ++need[c];
        int left = 0, right = 0;
        int count = 0;
        int start = 0; //用于记录符合要求的最小子串的开头
        int len = INT_MAX; //用于记录最小长度
        while(right < s.size()){
            auto c = s[right];
            ++right;
            if(need.count(c)){
                --need[c];
                if(need[c] == 0)    ++count;
            }

            while(count == need.size()){
                if(right - left < len){
                    start = left;
                    len = right  - left;
                }
                auto c = s[left];
                ++left;
                if(need.count(c)){
                    if(need[c] == 0)
                        --count;
                    ++need[c];
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

总之我们的目标是将字符查全，通过容器计数判断某个字符是否查全，哈希表的优点是可以在容器中快速定位到该字符并获取计数值，缺点是没有数组简单高效。而快速定位到某个字符这个功能，数组经过特殊处理也是能实现的（比如将字符转化为ASCII码，以ASCII码作为数组下标，就能实现快速定位），所以使用数组理论上会更快。使用数组需要注意的是：

如果使用两个数组，那就很简单，思路和两个哈希表几乎一模一样；

如果使用一个数组，需要考虑怎么初始化数组的值，因为我们会对数组中特定位置的值进行增加和减小的操作，就会导致缩小左边界的时候（会减小值）某些字符对应的值小于0(这是可能的，因为可能有重复字符的出现)，如果初始化做的不好，就很难将这些值和那些空位（非字符对应的数组下标）无法区分开来，这么说很抽象，还是看代码吧：

使用两个数组，之前哈希表耗时在60ms左右，数组的耗时则在10ms左右，确实快了很多：

class Solution {
public:
    string minWindow(string s, string t) {
        vector< int> need(58, 0), window(58, 0);//A(65) ~ z(122)范围内的ascii值范围
        for(auto c : t) ++need[c - 'A'];
        int left = 0, right = 0;
        int count = 0; //记录当前查全的字符个数
        int target = 0; //记录需要查全的字符个数
        for(auto c : need){
            if(c)   ++target;
        }
        int start = 0; //用于记录符合要求的最小子串的开头
        int len = INT_MAX; //用于记录最小长度
        while(right < s.size()){
            auto c = s[right] - 'A';
            ++right;
            if(need[c] > 0){
                ++window[c];
                if(need[c] == window[c])    ++count;
            }

            while(count == target){ //所有字符均查全
                if(right - left < len){
                    start = left;
                    len = right  - left;
                }
                auto c = s[left] - 'A';
                ++left;
                if(need[c] > 0){
                    if(need[c] == window[c])
                        --count;
                    --window[c];
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

如果只使用一个数组：

```cpp
class Solution {
public:
    string minWindow(string s, string t) {
        vector< int> need(58, 0);//A(65) ~ z(122)范围内的ascii值范围
        for(auto c : t) ++need[c - 'A'];
        int left = 0, right = 0;
        int count = 0; //记录当前查全的字符个数
        int target = 0; //记录需要查全的字符个数
        for(auto &c : need){
            if(c)   ++target;
            //数组need里面我们只是在某些部分（有字符ascii码对应的部分）填充了值，其他部分都初始化为0
            //我们通过need[c]的值是否大于0就能区分两者
            //但是下面会涉及到--need[c]的操作，这样某些填充了值的地方就会小于0
            //那么我们上面的判断依据就不管用了，所以才需要将那些未填充的地方的值设置的完全可以和填充过的地方区分开来
            //比如未填充地方全部设为INT_MIN，你填充过的地方即使会减小，也不可能一直减小到INT_MIN吧
            //而实际上取多少其实无所谓，能区分开就行，取个-1000就能区分开
            else    c = -1000; 
        }
        int start = 0; //用于记录符合要求的最小子串的开头
        int len = INT_MAX; //用于记录最小长度
        while(right < s.size()){
            auto c = s[right] - 'A';
            ++right;
            if(need[c] > -1000){
                --need[c];
                if(need[c] == 0)    ++count;
            }

            while(count == target){ //所有字符均查全
                if(right - left < len){
                    start = left;
                    len = right  - left;
                }
                auto d = s[left] - 'A';
                ++left;
                if(need[d] > -1000){
                    if(need[d] == 0)
                        --count;
                    ++need[d];
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};

其实数组占用空间本来就很小，使用两个数组就可以了，只使用一个数组运行效率上和使用两个的差别微乎其微，但是使用一个数组反而会更麻烦一点。