给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"示例 2：
输入：s = "a", t = "a"
输出："a"示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。提示：
1 <= s.length, t.length <= 105s和t由英文字母组成
**进阶：**你能设计一个在 o(n) 时间内解决此问题的算法吗？
解题思路：哈希表 + 滑动窗口 + 计数器
首先滑动窗口是通过暴力破解的优化规律得来的，这里就不加以解释了，主要优化的规律就是判断 right 指针是否可以不回退，这我们前面讲了很多次了，具体的可以自己画个图去分析分析！
然后还是一样，要借助哈希表来优化速度，因为这里字符串 s 和 t 由英文字母构成我们可以用数组来充当哈希表，但是因为其中包括了大小写字母，为了简单一些，我们干脆直接用 int hash[128] 大小的数组来充当哈希表，这样子省去了映射的麻烦，同时也减少了容器的开销！
此外，因为我们需要判断窗口内的字符映射的哈希表 hash 和字符串 t 的哈希表 alphahash 的出现次数是否一致，所以免不了要遍历 128 次的字符，通过之前的学习我们也知道可以用一个 count 变量来进行计数，只有当有效字符的时候才进行 count++ 和 count--，免去了遍历哈希表的操作！
但和 438. 找到字符串中所有字母异位词 这道题不太一样，这里要求的子串，其包含的有效字符个数是可以大于等于字符串 t 中该有效字符的个数的，此时我们要是让 count 单单统计出现的有效字符的个数的话那就错了！
为什么呢❓❓❓
假设字符串
s是"aabbc"，而字符串t是"abc"，如果count统计的是有效字符的个数的话，当遍历到s[2]也就是'b'的时候，此时count就为t.size()了，按照之前的做法就是更新结果，但是很明显，此时的结果并不是覆盖字符串t的，所以我们不能这么做！
这里正确的做法，是让 count 统计出现的有效字符的种类，而不是个数！
下面以上面的例一，结合算法过程来解释：
-
首先定义一个哈希表数组
alphahash用于统计字符串t中字符的出现个数，定义一个变量kinds统计字符串t中字符的种类。- 然后进行统计。
-
接着定义变量
count统计遍历途中有效字符的种类（注意不是次数），定义哈希表数组hash统计窗口内每个字符的出现次数，定义两个变量minlen和minleft用于记录最小长度以及起始位置。 -
初始化双指针
left和right，让right往后遍历-
相当于进窗口操作，即
hash[s[right]]++，并且判断一下此时s[right]是否出现个数达到了字符串t中该字符的出现次数- 即
hash[s[left]] == alphahash[s[left]]的话话说明这个种类就出现了，则count++ - 不是的话则不用管
- 即
-
接下来判断是否
count == kinds
- 是的话说明覆盖子串已经匹配，则此时更新最小长度和起始位置
minlen和minleft - 更新之后，就需要出窗口遍历后面的情况了！
- 出窗口即
hash[s[left]]--，但是在这之前需要先判断一下是否需要当前出窗口的字符s[left]是否会影响count- 如果说此时
hash[s[left]] == alphahash[s[left]]的话，等会出窗口了就不满足该字符的出现次数了，所以要让count-- - 其它情况则不需要管
- 如果说此时
- 字符出窗口之后记得让
left++
- 出窗口即
- 是的话说明覆盖子串已经匹配，则此时更新最小长度和起始位置
-
循环上述操作直到
count < kinds，也就是让滑动窗口的左边界不断地往后移动
-
-
最后
right走出界就结束！
class Solution {
public:
string minWindow(string s, string t)
{
int kinds = 0; // 统计字符的种类
int alphahash[128] = { 0 }; // 统计字符出现个数
for(auto c : t)
{
if(alphahash[c]++ == 0)
kinds++;
}
int left = 0; // 滑动窗口左边界
int count = 0; // 表示有效字符的种类（注意不是次数）
int hash[128] = { 0 }; // 统计窗口内每个字符的出现次数
int minlen = INT_MAX, minleft = 0;
for(int right = 0; right < s.size(); ++right)
{
// 进窗口
hash[s[right]]++;
if(hash[s[right]] == alphahash[s[right]]) // 达到t中该字符出现次数才count++
count++;
while(count == kinds)
{
// 先判断是否需要更新最小长度和起始位置
if(minlen > right - left + 1)
{
minlen = right - left + 1;
minleft = left;
}
// 出窗口
if(hash[s[left]] == alphahash[s[left]]) // 当出现次数即将小于t中该字符出现次数才count--
count--;
hash[s[left]]--;
left++;
}
}
return minlen == INT_MAX ? "" : s.substr(minleft, minlen);
}
};