算法分享——《滑动窗口》

🚍《长度最小的子数组》

🚲题目描述：

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

🥽代码实现：

class Solution 
{
public:
    int minSubArrayLen(int target, vector<int>& nums) 
    {
        int left = 0, right = 0, sum = 0, len = 1e9 + 1;
        while(right < nums.size())
        {
            sum += nums[right];
            while(sum >= target)
            {
                len = min(len, right - left + 1);
                sum -= nums[left];
                ++left;
            }
            ++right;
        }
        return len == 1e9 + 1 ? 0 : len;
    }
};

🎪代码解析：

滑动窗口其实是属于双指针算法的一种，针对本道题目，如果我们使用最传统的暴力解法来实现算法，我们可以定义两个指针 left 和 right 再定义一个sum用来保存当前记录。

然后开始遍历数组，right指针不断往右遍历然后加到sum之中，然后再判断是否大于等于target，如果满足大于等于 target 就停止然后让left++，然后再让right回来然后一直不断进行遍历，这样的时间复杂度就变成了O(N^2)，效率太低下了。

其实我们可以利用单调性来解决这种问题，我们想要使得sum >= target，其实只要right不断向右移动然后与sum相加就好了，若是判断满足了sum >= target，这时也不需要进行重置，而是直接让sum -= nums[left]再让left++若是sum依然满足sum>=target则继续sum -= nums[left]和left++

• right不断向右找数据（target == 7）
  

• 此时sum >= target，则 sum -= nums[left]再让left++
  

• 然后又不满足sum >= target了，所以right++再继续sum += nums[right]

  

• 然后继续sum -= nums[left]再left--，最后sum == 7还是大于等于target，但是len变小了。
  

• 又来，所以继续
  

• 然后right++再sum += nums[right]
  

• 然后继续sum -= nums[left]再left--
  

• 又来，所以继续
  

此时循环结束，最小的区间就是2，答案就出来了。那么我们是否可以总结出一个规律呢？我们发现这种对于利用双指针同向处理数组的算法可以称为：“滑动窗口”。

我们会发现有一个方框（窗口）在一直不断地进数据和出数据，是个动态的数据，而这里面的数据都是满足>=target的，而我们要不断的判断，因此这种算法最适合用来解决这种同向双指针的问题。

最后我们还要小心示例3这种情况：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0

所以最后的结果要注意，如果len是INT_MAX或1e9 ，我们就要返回0。

🚍《无重复字符的最长子串》

🚲题目描述：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长连续子字符串 的长度示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子字符串是 "abc"，所以其长度为 3。

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子字符串是 "b"，所以其长度为 1。

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

示例 4:

输入: s = ""
输出: 0

🥽代码实现：

class Solution 
{
public:
    int lengthOfLongestSubstring(string s) 
    {
        int left = 0, right = 0, len = 0, hash[128];
        for(; right < s.size(); ++right)
        {
            hash[s[right]]++;
            while(hash[s[right]] > 1) hash[s[left++]]--;
            len = max(len, right - left + 1);
        }
        return len == 0 ? s.size() : len;
    }
};

🎪代码解析：

我们先拿一个来举例子，题目的要求就是找到一个最大的无重复字符的子串，所以刚上来我们当然可以想到用暴力的解法来解决这道题，但是我们的时间复杂度当然会非常高，所以我们不采用这个方法。

我们先来以暴力的视角来看看这道题的解法：
让right指针不断向右遍历，对于判断该字符是不是已经重复，我们只需要建立一个哈希表即可，然后将遍历到的字符存放至哈希表里就好了。
只要在遍历的过程通过哈希表发现了重复的字符，我们就让left++，然后再让right回到left之后的位置。

但是这会出现一个问题，就是每次我的right遍历走到了同一个位置，还是会出现重复的字符：

这就是为什么暴力做法时间复杂度高的原因。

因此我们可以当right通过哈希表找到重复的字符后，就让right停下来，然后让left不断向右遍历，所经过的字符都让它们在哈希表对应的位置-1，直到找到重复的字符，然后让对应的哈希表位置-1，再指向下一个位置。这样我们就完成了去除重复字符的操作！

遇到了重复的字符，然后让操作left：

此时就不存在一个新的[left, right]的区间内，就不存在重复的字符啦，这就完成了**“进窗口和出窗口的过程”！所以这道题的算法解决就自然而然的衍生到了——“滑动窗口”**

最后我们只需要在循环的结尾记录这个“窗口”的长度，同时还要注意，当题目给了一个无字符的数组，我们只要判断它之后直接返回0就好了。

🚍《最大连续1的个数 III》

🚲题目描述：

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 0], K = 2
输出：6
解释：[1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。

示例 2：

输入：nums = [0, 0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1], K = 3
输出：10
解释：[0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。

🥽代码实现：

class Solution 
{
public:
    int longestOnes(vector<int>& nums, int k) 
    {
        int sumzero = 0;
        int len = 0;
        for(int left = 0, right = 0; right <nums.size(); ++right)
        {
            if(nums[right] == 0) ++sumzero;
            while(sumzero > k)
                if(nums[left++] == 0) --sumzero;
            len = max(len, right - left + 1);
        }
        return len;
    }
};

🎪代码解析：

我们可以对问题进行深入理解理解，首先题目所讲的是K，它是一个最大的范围，我们可以翻转1次也可以翻转K - 1次也都可以。

如果用暴力来解决这道题的话，就需要一个一个的将0转换成1，这样子的话代码实现过于复杂了。
我们可以简化一下题目描述，我们其实想找到的是一个子数组，这一个子数组中有K个0或K个以下数的0变成1后能满足最大的长度。
所以我们只需要通过left指针和right指针遍历这个数组，统计0的个数，然后判断是否超过了K，如果超过了K就记录这个长度，然后再让left++让right回来继续遍历，然后一个一个的判断。这其实也是一种暴力解法，但是好在我们把问题简化了。

现在我们可以来尝试模拟一遍：

如果此时我们对0的个数进行统计之后，结果大于k了：

我们left++然后再让right回到left这里：

那当我们的right还是会经过那两个0，我们又要再让left++，right也又要回来

这不是上面那个《无重复字符的最长子串》和《长度最小的子数组》结合起来后的题目嘛？
当我们的0的个数大于2时，我们就没必要再让right回来了，只要让left一直向右移，遇到0就让统计0的个数的变量减一，知道正好等于就让left停下来，然后再进行判断。这不就是滑动窗口嘛。

🚍《将 x 减到 0 的最小操作数》

🚲题目描述：

给你一个整数数组 nums 和一个整数 x 。每一次操作时，你应当移除数组 nums 最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，需要 修改 数组以供接下来的操作使用。

如果可以将 x 恰好 减到 0 ，返回 最小操作数 ；否则，返回 -1 。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除后两个元素，将 x 减到 0 。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除后三个元素和前两个元素（总共 5 次操作），将 x 减到 0 。

🥽代码实现：

class Solution 
{
public:
    int minOperations(vector<int>& nums, int x)
    {
        int n = 0, sum = 0, len = -1, target = 0;
        for(auto num : nums) n += num;
        target = n - x; // 正难则反
        if(target < 0) return -1;
        
        for(int left = 0, right = 0; right < nums.size(); ++right)
        {
            sum += nums[right];
            while(sum > target) sum -= nums[left++];
            if(sum == target) len = max(len, right - left + 1);
        }
        return len == -1 ? len : nums.size() - len;
    }
};

🎪代码解析：

刚拿到这道题目，我的第一反应是从小到大进行排序，编写代码之后尝试跑了一下，发现三个示例都对，但是后面就会不断的报错，所以我就不断的修改再修改，好不容易修改好了，再一跑，第一个示例就跑不过了。
于是我就看了一下解题思路，发现我们既然我们很难一会从左边判断，一会又从右边判断，因此我们不妨换种思路来解，俗称——正难则反

对于示例一来说，x == 5，我们的最终结果是直接对最后两个数2和3进行操作，就能将x变为0。因此操作这2个数正是我们需要操作的最小操作数。

说的确实没错，但是数一旦多起来了我们可能一会去左边操作一下，再到右边操作一下，实在是太复杂了！！

但是每个示例总会存在那个最小操作数，但是他们不连续！而除去作为操作数的其它元素，它们却是连续的！

就比如上面示例的1 1 4,元素，他们是连续的！

所以呀，我们既然要找最小的操作数，我们就可以找到除身为最小操作数的其他数

现在问题转化了，我们现在要找到一个子数组，这个子数组的各个元素要等于 总元素数 - x，那针对于这个转化，解题思路不就是我们的第一道题吗——《长度最小的子数组》？但是这里我们要找的是正好等于target的子数组，而且还得是最大长度的子数组！所以还是使用滑动窗口的思路来解决！

1. 先统计各个元素之和的大小n
2. 计算出target = n - x
3. 使用滑动窗口算法，找到最大的子数组满足各个元素之和 == target！

[!NOTE]

这里存在两个细节问题：

1. 一定要找到各个元素之和正好等于target的子数组后，再统计子数组长度，不然假如你统计了一个大于target的子数组，这个数组长度为6，但是刚刚好等于target的子数组实际才为3个长度，此时你的len就根本变不了了，所以你需要在正好的时候统计长度！

2. 然后就是你运行你的算法后，题目会给你报错，例子如下图：
   

   这就代表你的target变成负数了，那么这时候无论你怎么滑动窗口，你都不可能达到target，所以直接return -1就好了！

🚍《水果成篮》

🚲题目描述：

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。

🥽代码实现：

class Solution 
{
public:
    int totalFruit(vector<int>& fruits) 
    {
        int hash[100001] = {0}, sum = 0, len = 0;
        for(int left = 0, right = 0; right < fruits.size(); ++right)
        {
            if(hash[fruits[right]] == 0) sum++;
            hash[fruits[right]]++; // 进窗口

            while(sum > 2) // 判断
            {
                // 出窗口
                hash[fruits[left]]--;
                if(hash[fruits[left]] == 0) sum--;
                ++left;
            }
            len = max(len, right - left + 1);
        }
        return len;
    }
};

🎪代码解析：

关于水果成篮，将问题简化，就是我们要在一个数组中找到连续出现了两个数字的最大长度的子数组，这两个数字可以出现多个，但只能是这两个数字。那么还是使用“滑动窗口”来解决。

我们可以用哈希表来记录我们出现过的数字，然后用sum来记录出现的数字的种类个数，记住是数字种类个数，sum要永远小于等于2。

我们在使用right指针向右遍历的之前，需要先判断当前right的位置映射到哈希表中的位置是否为0？因为我们可能会出现重复数字，在判断完之后我们就可以选择是否对种类个数进行++。这个过程就是我们的“进窗口”操作。

如果我们找到了一个新的数，先看看sum是不是小于2，如果是小于2那就继续进窗口，但是sum如果大于2了，那我们就要出窗口了。
出窗口我们也需要注意很多细节，我们出窗口目的是要让sum变为2，即让数字的种类从3变为2，因此我们一定要让一种数字的哈希表映射为0时，才能--sum！

🚍《找到字符串中所有字母异位词》

🚲题目描述：

给定两个字符串 s 和 p，找到 s 中所有 p 的 变位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

变位词 指字母相同，但排列不同的字符串。

示例 1：

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的变位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的变位词。

示例 2：

输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的变位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的变位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的变位词。

🥽代码实现：

class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ans;
        int hash_s[26] = {0}, hash_p[26] = {0}, len = p.size(), count = 0;
        for(auto ch : p) hash_p[ch - 'a']++;

        for(int left = 0, right = 0; right < s.size(); ++right)
        {
            hash_s[s[right] - 'a']++;
            if(hash_s[s[right] - 'a'] <= hash_p[s[right] - 'a']) 
            {
                ++count;
            }
            if(count == len) ans.push_back(left);
            if(right - left + 1 == len)
            {
                if(hash_s[s[left] - 'a'] <= hash_p[s[left] - 'a'])
                {
                    --count;
                }
                hash_s[s[left] - 'a']--;
                ++left;
            }
        }
        return ans;
    }
};

🎪代码解析：

对于查找异位词，如果依然采取我们之前对于滑动窗口的那种算法思路来解决这道题目，不仅仅是思路，在编写代码实现的时候将是十分困难的。

我们在分析题目的时候，其实就是要满足在s这个字符串中，找到一个子串，使这个子串具有的元素及个数 == p这个string的元素及个数。对于这种统计个数又统计元素的，我们当然可以使用两个哈希表来解决，当然和之前一样用数组开辟的哈希表即可解决。

既然我们也简化问题了，那其实我们只需要以p这字符串的长度为单位，不断比对s字符串出现的元素就好了，如下图：

因为p仅仅只有三个元素，因此我们在s中比对哈希表的时候，也仅仅需要以长度为3为单位进行比对，如下：

通过规律来看，其实每次判断，只需要right++和left++还有更新哈希表即可，在这个大小固定的窗口里进行查找就好了。 现在你可以先按照这个规律试试编写代码，思路已经告诉你了，而且按道理来说，这道题到目前就已经结束了，但是后面还会有一道题，不是用字符了，而是用字符串的，对于那道题目，如果单单使用哈希表和窗口来判断，就有点麻烦了，接下来我们会优化这道题目。
优化前的代码：

class Solution 
{
public:
    vector<int> findAnagrams(string s, string p) 
    {
        vector<int> ans;
        int hash_s[26] = {0}, hash_p[26] = {0}, len = p.size(), flag = 1;
        for(auto ch : p) hash_p[ch - 'a']++;

        for(int left = 0, right = 0; right < s.size(); ++right)
        {
            hash_s[s[right] - 'a']++;
            if(hash_s[s[right] - 'a'] > hash_p[s[right] - 'a']) 
            {
                if(s[left] == s[right]) 
                    hash_s[s[left++] - 'a']--;
                else
                    while(hash_s[s[right] - 'a'] > hash_p[s[right] - 'a']) hash_s[s[left++] - 'a']--;
            }
            
            if(right - left + 1 == len)
            {
                ans.push_back(left);
                hash_s[s[left++] - 'a']--;
            }
        }
        return ans;
    }

🚀优化代码：

上面所运用的算法思路其实与之前的思路相似，准确来说与《无重复字符的最长子串》题目相似。

我们再回顾一下满足的情况，其实就是在指定的长度下，在s中判断即可。而关键的问题，就是在p中找到满足s中的全部元素及其个数，因此我们可以定义一个变量count来帮助我们统计。

这时我们最开始的情况，黑色的a、b、c代表s字符串的哈希表，红色的代表p字符串中的哈希表。每次right访问一个字符就往哈希表里++一次。

• 如果hash1[in] <= hash2[in] 我们就让计数器count++

  
  此时字符c出现的个数为1，满足hash2的c个数，所以count++.

  
  此时字符c出现的个数为1，不满足hash2的c个数，所以不操作count.

  
  此时字符a出现的个数为1，满足hash2的a个数，所以count++.

• 判断当count == len的时候

  如果count == len那我们就直接可以确定left找到了异位词，将left的下标保存就好了。
  但是如果不满足，那我们就还有进行判断，正如上图这种情况所示。

• 判断right - left + 1 == len

  如果此时我的“窗口”的长度正好等于p字符串的长度，那么我们就得让left++了，前面讲过了为什么要加加。

  但是我们在让left++的时候，别忘了left对应的哈希表也要对应的减小。

  这个时候我们也要对count进行操作，如果hash1[out] <= hash2[out]的话，就要count--，举个例子：
  

  因为此时的字符c出现的个数为2，不满足小于等于hash2的字符c的个数，所以我们不需要让count--，只需要让对应的哈希表减一即可。
  

  然后再进入循环，让right++，再让哈希表对应的字符数加一：
  

  因为b的个数满足小于等于hash2的b的个数，所以count++.
  

  这个时候就可以直接保存left对应的下标了。

🚍《串联所有单词的子串》

🚲题目描述：

给定一个字符串 s 和一个字符串数组 words。 words 中所有字符串 长度相同。

s 中的 串联子串 是指一个包含 words 中所有字符串以任意顺序排列连接起来的子串。

• 例如，如果 words = ["ab","cd","ef"]， 那么 "abcdef"， "abefcd"，"cdabef"， "cdefab"，"efabcd"， 和 "efcdab" 都是串联子串。 "acdbef" 不是串联子串，因为他不是任何 words 排列的连接。

返回所有串联子串在 s 中的开始索引。你可以以 任意顺序 返回答案。

示例 1：

输入：s = "barfoothefoobarman", words = ["foo","bar"]
输出：[0,9]
解释：因为 words.length == 2 同时 words[i].length == 3，连接的子字符串的长度必须为 6。
子串 "barfoo" 开始位置是 0。它是 words 中以 ["bar","foo"] 顺序排列的连接。
子串 "foobar" 开始位置是 9。它是 words 中以 ["foo","bar"] 顺序排列的连接。
输出顺序无关紧要。返回 [9,0] 也是可以的。

示例 2：

输入：s = "wordgoodgoodgoodbestword", words = ["word","good","best","word"]
输出：[]
解释：因为 words.length == 4 并且 words[i].length == 4，所以串联子串的长度必须为 16。
s 中没有子串长度为 16 并且等于 words 的任何顺序排列的连接。
所以我们返回一个空数组。

示例 3：

输入：s = "barfoofoobarthefoobarman", words = ["bar","foo","the"]
输出：[6,9,12]
解释：因为 words.length == 3 并且 words[i].length == 3，所以串联子串的长度必须为 9。
子串 "foobarthe" 开始位置是 6。它是 words 中以 ["foo","bar","the"] 顺序排列的连接。
子串 "barthefoo" 开始位置是 9。它是 words 中以 ["bar","the","foo"] 顺序排列的连接。
子串 "thefoobar" 开始位置是 12。它是 words 中以 ["the","foo","bar"] 顺序排列的连接。

🥽代码实现：

class Solution 
{
public:
    vector<int> findSubstring(string s, vector<string>& words)
    {
        vector<int> ans;
        unordered_map<string, int> word_map;
        for (const auto& w : words) word_map[w]++;

        int len = words[0].size(), sz = words.size();
        for (int i = 0; i < len; ++i)
        {
            unordered_map<string, int> s_map;
            for (int left = i, right = i, count = 0; right + len <= s.size(); right += len)
            {
                string in = s.substr(right, len);
                s_map[in]++;
                if (word_map[in] && s_map[in] <= word_map[in]) count++;
                if (count == sz) ans.push_back(left);
                if ((right - left) / len == sz - 1)
                {
                    string out = s.substr(left, len);
                    if (word_map[out] && s_map[out] <= word_map[out]) count--;
                    s_map[s.substr(left, len)]--;
                    left += len;
                }   
            }
        }
        return ans;
    }
};

🎪代码解析：

我们在上一道题的优化访问介绍过，我们会遇到一种题目是利用哈希表统计字符串的，本题目正是需要用到上述题目的优化算法的！如果你明白了上道题利用count来统计的算法思路，那么对于该题目相信你也可以迎刃而解。

因为这道题我们是要利用哈希表来统计string类型的字符串，因此我们不能再用数组来代替哈希表了，应该使用unordered_map<string, int>来统计。

为什么我说这道题算法思路和上面那道题一样呢？是因为我们可以将一个一个的单词简化，因为单词内部的字母顺序是不会变的，而且我们的目标数组中的所有单词长度都是一样的，正因如此我们每次就找一个单词然后就可以通过单词长度跳到下一个单词就好了！

关于进窗口和出窗口的判断和上题一致，关于count计数器的判断也是一样的，在这里我就不过多赘述。

值得注意的就是判断条件：

• right在遍历单词的时候，是要将当下的单词，以特定的单词长度加入到哈希表里。而right的遍历范围是不能越过数组的！所以我们最好在for循环判断里，写成right + len <= s.size()
• 正因为我们是要在一堆字母中判断是否出现特定的单词，由于不一样的排列组合我们还需要不断改变left的起始位置：
  
  当然我们只需要移动对应的单词长度就好了，因为后面都重复了所以不用再考虑。
• 还有就是在判断是否需要出窗口的时候，出窗口的条件是我们已经进窗口的单词数，等于我们需要查找的单词数，对于统计单词数我们可以使用这个判断：(right - left) / len == sz - 1

然后就是要记得在每次移动left一定要使你的哈希表里面的值都清干净，count的值也要清干净，所以直接在for循环里面定义即可，退出循环还可以主动释放。

还有存在一个语法效率问题，就是针对于两个哈希表对应的单词数量的大小的判断，如果我的word_map没有某个单词我们还有创建，这个是会降低效率的，所以我们直接把判断语句写成：

if (word_map[in] && s_map[in] <= word_map[in]) count++;
if (word_map[out] && s_map[out] <= word_map[out]) count++;

这道题目我讲解的很简单，最主要的算法思路还是建立在上一道题目的算法实现上。

🚍《最小覆盖子串》

🚲题目描述：

给定两个字符串 s 和 t 。返回 s 中包含 t 的所有字符的最短子字符串。如果 s 中不存在符合条件的子字符串，则返回空字符串 "" 。

如果 s 中存在多个符合条件的子字符串，返回任意一个。

注意： 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC" 
解释：最短子字符串 "BANC" 包含了字符串 t 的所有字符 'A'、'B'、'C'

示例 2：

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

示例 3：

输入：s = "a", t = "aa"
输出：""
解释：t 中两个字符 'a' 均应包含在 s 的子串中，因此没有符合条件的子字符串，返回空字符串。

🥽代码实现：

class Solution 
{
public:
    string minWindow(string s, string t) 
    {
        string ans;
        int hash_s[130] = {0}, hash_t[130] = {0}, count = 0, len = INT_MAX;
        for(const auto& ch : t) hash_t[ch]++;

        for(int left = 0, right = 0; right < s.size(); ++right)
        {
            hash_s[s[right]]++;
            if(hash_s[s[right]] <= hash_t[s[right]]) count++;
            while(count >= t.size())
            {
                if(len > right - left + 1) 
                {
                    len = right - left + 1;
                    ans = s.substr(left, len);
                }
                if(hash_s[s[left]] <= hash_t[s[left]]) count--;
                hash_s[s[left++]]--;
            }
        }
        return ans;
    }
};

🎪代码解析：

与前面的算法思路一致，我们还是需要借助哈希表来统计字符出现的次数，当然这次我们这里用数组来代替unordered_map就好了。

同样是定义两个指针实现滑动窗口，我们可以让right不断的去遍历然后将遍历到的元素写入哈希表，这一步是进窗口。
同样的，我们结合上面的优化算法，定义一个count计数器，来判断两个哈希表对应元素的个数。
当hash1[in] <= hash2[in]说明此时的子串对应的元素还是太少，因此count加一

当我们的count == sz时，说明我们的right和left之间已经存在了我们需要的元素！
所以我们让right不动，通过移动left来实现出窗口的操作，但在出窗口之前仍然需要判断是否要让count减一。
当hash1[out] <= hash2[out]，说明将需要的元素移出了窗口！

按照这样的进窗口和出窗口操作，同时我们还要更新子串。

更新子串只要看看right 和 left之间的长度和上一次的子串长度进行比较就好了，如果新的长度较小，就利用string的接口函数substr来记录新的最小子串！