给出两个字符串 s和 t，要求在 s中找出最短的包含 t中所有字符的连续子串。
数据范围：0 > |S|,|T| \le100000>∣S∣,∣T∣≤10000，保证s和t字符串中仅包含大小写英文字母
要求：进阶：空间复杂度O(n)O(n)， 时间复杂度O(n)O(n)
例如：
S ="XDOYEZODEYXNZ"S="XDOYEZODEYXNZ"
T ="XYZ"T="XYZ"
找出的最短子串为"YXNZ""YXNZ".
注意：
如果 s中没有包含 t中所有字符的子串，返回空字符串 “”；
满足条件的子串可能有很多，但是题目保证满足条件的最短的子串唯一。
示例1
输入：
"XDOYEZODEYXNZ","XYZ"
复制返回值：
"YXNZ"
复制
示例2
输入：
"abcAbA","AA"
复制返回值：
"AbA"
这个题刷了很久没搞定，看了大牛的操作才明白。大概思路跟我一致，细节处理人家很到位。
class Solution {public:/*** * @param S string字符串 * @param T string字符串 * @return string字符串*/string minWindow(string S, string T) {int minLen = INT32_MAX;int left = 0,right = 0,count = 0,start = 0;unordered_map<char, int> target,window;for(char c : T){target[c]++;}while(right < S.size()){char c = S[right];right++;if(target.count(c)){window[c]++;if(window[c] == target[c]){count++;}}while(count == target.size()){char c = S[left];if (right-left < minLen) {start = left;minLen = right-left;}if(target.count(c)){if(target[c] == window[c]){break;}window[c]--;}left++;}}return minLen == INT32_MAX ? "" : S.substr(start,minLen);}};
如果觉得《滑动窗口大杀器 牛逼》对你有帮助，请点赞、收藏，并留下你的观点哦！
