LeetCode #76 最小覆盖子串
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。 注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC"
示例 2：
输入：s = "a", t = "a" 输出："a"
提示：
-
1 <= s.length, t.length <= 105 s 和 t 由英文字母组成
进阶：你能设计一个在 o(n) 时间内解决此问题的算法吗？
在题解中看到的思路，最初我的想法和这个一样，但是没想好怎么处理其他的字符（但其实发现根本不用处理其他的字符）
思路是这样的，用个哈希保存t中字符的数量，遍历s字符串，如果哈希中的值都为0(怎么判断都为0呢。。用一个变量，记录t的总数，如果该变量为0，说明已经包含了字符串t)，说明目前从zuo到you已经包含了字符串t
这时候改变zuo的位置，因为左面可能有一些冗余的或者不是t中的字符，当发现哈希表中某个值为0，说明目前从zuo到you的字符串是当前存在字符串t的最小字符串。判断保存最短的
然后左面的字符移动一位，移动一位之后从zuo到you的字符串已经不包含t了，然后重复执行之前的步骤
可以把这个哈希表理解为，当ma[x]=5，说明目前还缺5个字符x，ma[x]=-2，说明当前从zuo到you的字符串里已经多了2个x
class Solution { public: int pd(char ss,string s){ for(int i = 0;i < s.size();i++){ if(s[i] == ss) return 1; } return 0; } string minWindow(string s, string t) { map<char,int> ma; for(int i = 0;i < t.size();i++) ma[t[i]]++; int zuo = 0,you = 0; int all = t.size(); int out_zuo = 0,out_you = s.size() + 1; while(you < s.size()){ if(ma[s[you]] > 0) all--; ma[s[you]]--; if(all == 0){ while(zuo <= you){ if(ma[s[zuo]] == 0) break; ma[s[zuo]]++; zuo++; } if(you - zuo < out_you - out_zuo){ out_you = you; out_zuo = zuo; } ma[s[zuo]]++; all++; zuo++; } you++; } if(out_you == s.size() + 1) return ""; string out = ""; for(int i = out_zuo;i <= out_you;i++) out += s[i]; return out; } };
