给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a"
输出："a"
解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
思路和算法
本问题要求我们返回字符串 sss 中包含字符串 ttt 的全部字符的最小窗口。我们称包含 ttt 的全部字母的窗口为「可行」窗口。
我们可以用滑动窗口的思想解决这个问题。在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 rrr 指针，和一个用于「收缩」窗口的 lll 指针。在任意时刻，只有一个指针运动，而另一个保持静止。我们在 sss 上滑动窗口，通过移动 rrr 指针不断扩张窗口。当窗口包含 ttt 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。
如何判断当前的窗口包含所有 ttt 所需的字符呢？我们可以用一个哈希表表示 ttt 中所有的字符以及它们的个数，用一个哈希表动态维护窗口中所有的字符以及它们的个数，如果这个动态表中包含 ttt 的哈希表中的所有字符，并且对应的个数都不小于 ttt 的哈希表中各个字符的个数，那么当前的窗口是「可行」的。
注意：这里 ttt 中可能出现重复的字符，所以我们要记录字符的个数。
1 class Solution {
2 public:
3 unordered_map<char,int>ori,cnt;
4
5 //判断窗口中是否含有t中所有字符
6 bool check()
7 {
8 //迭代器的一种写法
9 for(const auto &p:ori)
10 {
11 if(cnt[p.first]<p.second)
12 return false;
13 }
14 return true;
15 }
16
17 string minWindow(string s, string t) {
18
19 //创建t的字符表
20 for(int i=0;i<t.length();i++)
21 {
22 ori[t[i]]++;
23 }
24
25 int l=0;
26 int r=0;
27 int length=INT_MAX;
28 int ansl=-1;
29
30 while(r<int(s.size()))
31 {
32 //当前最右端的字符在t中则对当前窗口的字符表进行更新
33 if(ori.find(s[r])!=ori.end())
34 cnt[s[r]]++;
35
36 //假如搜索到的窗口中含有t中所有字符
37 while(check()&&l<=r)
38 {
39 //更新长度
40 if(r-l+1<length)
41 {
42 length=r-l+1;
43 ansl=l;
44 }
45 //右移最左端，同时也要更新当前窗口的字符表
46 if(ori.find(s[l])!=ori.end())
47 {
48 cnt[s[l]]--;
49 }
50 l++;
51 }
52 r++;
53 }
54
55 return ansl==-1?string():s.substr(ansl,length);
56 //学习一下这种写法！！！
57
58 }
59 };
标签：子串,字符,窗口,最小,ttt,76,字符串,滑动 From： https://www.cnblogs.com/saucerdish/p/17805851.html