题目描述

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

样例

输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"

算法1

(双指针中的滑动窗口)

当我们遇到子串和链表的问题，一般来说都会用到双指针，这里是双指针滑动窗口的运用.
1.我们首先得知道什么情况下，right指针需要向右移动: 当前的元素没有达到题目的要求
2.right指针向右移动的情况下，怎样更新数据:我们需要数据结构去承载这些数据
3.left指针向右移动的情况: 当窗口里面的元素满足题意的时候，left移动寻找最优结构.
4.一直这样来回重复，然后知道right指针结束.

C++ 代码

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map <char,int> windows,need;
        for (char c: t) need[c]++;
        int left = 0,right = 0,start = 0;
        int length = 1e6;
        int cnt = 0;//记录个数
        while(right < s.size()){
            char d = s[right++];
            if (need.count(d)){//是否为目标程序
                windows[d]++;
                if (windows[d] == need[d]){ //是的话，就++;
                    cnt ++;
                }
            }
            while(cnt == need.size()){//维护窗口
                if (right - left < length){//找最优的答案,里面的逻辑是怎样的
                    length = right - left;
                    start = left;
                }
                char c = s[left++];//我们往里面添加元素后面记得我们要维护窗口的稳定性
                if (need.count(c)){
                    if (need[c] == windows[c]){
                        cnt --;
                    }
                    windows[c]--;
                }
            }
        }
        return length == 1e6 ? "" : s.substr(start,length);
    }
};