题目内容

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 “” 。请设计一个在 o(n) 时间内解决此问题的算法？

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

示例

示例 1：

输入：s = “ADOBECODEBANC”, t = “ABC”
输出：”BANC”

示例 2：

输入：s = “a”, t = “a”
输出：”a”

提示

1、1 <= s.length, t.length <= 10^5
2、s 和 t 由英文字母组成

题解

本题采用双指针算法求解。

具体，我们思路如下：

我们以i代表的字符为终点，以j代表的字符为起点的子串作为我们每次检查的子串用于判断是否覆盖t即可。

当然，之所以可以使用双指针算法，是因为当i向后移动时，是处于当前j未匹配到的情况，因此j之后的动作一定是在原地不懂或者向后移动，因此j指针是存在单调性的，因此可以使用双指针算法。

当然，如果直接按照这种方式求解，一定会超时，因为这是O(n^2)的时间复杂度。

我们来看看优化方式：

首先，使用hash表统计 i,j 之间每种字符出现的次数

然后，每次遍历需要的操作如下：

1、加入 s[i]，同时更新哈希表；
2、检查 s[j] 是否多余，如果是，则移除 s[j]；
3、检查当前j到i中是否已经满足 T 中所有字符，如果是，则判断并更新答案，即判断i-j+1的长度是否小于当前最小值即可。

具体，请看代码。

代码

class Solution {
public:
    string minWindow(string s, string t) {
        //求对于每个终点i，求一个离i的左边最近的j，使得i-j+1最小，且包含T中的每个字符即可。
        unordered_map<char,int> hs,ht;//分别代表s中字幕出现的次数和t中字母出现的次数
        for(auto c: t) ht[c]++;
        string res;
        int cnt = 0;//记录当前有效字符的个数
        for(int i = 0, j = 0; i < s.size(); i++){
            hs[s[i]] ++;
            if(hs[s[i]] <= ht[s[i]]) cnt++;
            while(hs[s[j]] > ht[s[j]]) hs[s[j++]]--;
            if(cnt == t.size()){
                if(res.empty() || i - j + 1 < res.size())
                    res = s.substr(j,i - j + 1);
            }
        }
        return res;
    }
};