题目链接：76. 最小覆盖子串

题解：

滑动窗口界的一大难题！

题目简述：

给定两个字符串，从一个串找到包含另一个字符串所有字符的子串，并找到最短的一个！

题解：

双指针算法：

两个指针都从起点从左向右，i指针指向该区间终点，j指针指向该区间起点，维护一段区间i ~ j使得该区间包含待匹配字符串的每个字符。

具体做法：

  • 为了判断该区间是否包含待匹配字符串的每个字符，我们使用一个哈希表动态存储该区间每个字符出现的次数
  • 使用变量cnt统计该区间有效字符个数（即待匹配字符串中对应匹配的字符），只要该区间当前字符个数小于等于待匹配字符串的当前字符个数，即为有效字符，进行统计，即hs[s[j]] <= ht[s[j]]
  • 维护起点j，若新加入的字符导致hs[s[j]] > ht[s[j]]，则说明起点j可以后移，即 hs[s[j ++ ]] --，还得保证起点j一定是一个合法字符（即起点一定不是待匹配字符串没有的字符，如：ADOBECODEBA 匹配 ABC，应该要将起点A删去，再将DOBECODE删去。剩下BA，即这里是需要while来控制的）
  • 当cnt == t.size()：即该区间已经匹配，进行更新res即可，res为空也要更新！

使用双指针算法的条件：一定要有单调性，即一个指针后移，另一个指针也要后移！

对于本题：i' < i, j < j'时，当i向后走到i'，由于原来的j ~ i已经匹配，所以j一定不会往前走到j'，即j一定会不动或者向后走，这样就保证了单调性！

时间复杂度： O(n)

AC代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> hs, ht;
        for(auto& c : t) ht[c] ++;
        int cnt = 0;
        string res;
        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;
    }
};