1
class Solution
2
{
3
    public:
4
      string minWindow(string s,string t)
5
        {
6
            unordered_map<char,int> slideWindow; //滑动窗口中的各个字母及其个数
7
            unordered_map<char,int> targetString; //目标字符串的各个字母及其个数
8

9
            //传入目标字符串的数据
10
            for(char c : t) targetString[c]++;
11
            int left = 0,right = 0; //滑动窗口左右侧
12
            int length = s.size(); //S串的长度
13
            int start = 0,minLength = INT_MAX; //最小字串的开始位置 以及最短长度
14
            int windowCount = 0; //滑动窗口中字母的种类数 当该数据与targetString中的字符种类数相等时开始进行缩小处理
15

16
            //扩大窗口开始查询
17
            while(right < length) //right会停在刚好满足目标串字母数的最后一个字母处 可能不会到S串底
18
            {
19
                if(targetString.count(s[right])) //只对Target字符串中的字母进行记录
20
                {
21
                    slideWindow[s[right]]++; //对right处对应的字母数量进行记录
22
                    if(slideWindow[s[right]]==targetString[s[right]])
23
                    {
24
                        windowCount++; //如果滑动窗口中当前字母的数量与Target字符串中的数量能够对应 则记录该种字母
25
                    }
26
                }
27
                right++; //滑动窗口扩大 继续寻找所需要的字符
28
                //如果S串确实包含了T串中所有字母 则开始缩小滑动窗口寻找最小串 否则继续执行该循环 扩大滑动窗口
29
                while(windowCount == targetString.size())
30
                {
31
                    //因为已经能够在S串中找到目标串的所有字母了 所以先要记录当下的最小串 再看看能不能找到更小的
32
                    if(right - left < minLength)
33
                    {
34
                        start = left; //更新起始位置
35
                        minLength = right - left; //更新最短长度
36
                    }
37

38
                    //接下来进行缩短窗口的处理
39
                    char c_left = s[left]; //取出窗口左侧的字母
40
                    if(targetString.count(c_left)) //如果当前字母在目标串中存在
41
                    {
42
                        slideWindow[c_left]--; //将该字母移除 同时减少数量
43
                        if(slideWindow[c_left] < targetString[c_left]) //如果滑动窗口串中的该字母数量已经不满足目标串 则结束循环 继续扩大窗口                                     或者因为right到达尾部而直接结束循环
44
                        {
45
                            windowCount--; //通过windowCount != targetString.size() 结束循环
46
                        }
47
                    }
48
                    left++; //如果不是目标字符串的字母 直接将其移除 收缩窗口
49
                }
50
            }
51
            //进行收尾处理
52
            return minLength == INT_MAX ? "" : s.substr(start,minLength);
53
        }
54
};
55

56
时间复杂度O(n) 13ms 并非最优 空间复杂度O(n) 11.4MB  并非最优