76. 最小覆盖子串
- 注意题目给出的两点限制
-
根据示例，我们可以知道要求的是一个满足条件的连续子串
-
限制1告诉我们是找最小连续子串问题
- 因此考虑滑动窗口
双指针实现滑动窗口思路？
- 见代码部分
class Solution {
public:
string minWindow(string s, string t) {
unordered_map unordered_map_char_to_int;
for (auto p : t)
++unordered_map_char_to_int[p];
int l = 0, r = 0;
int size_s = s.size(), size_t = t.size();
int min_l = 0, min_size = size_s + 1; // 记录位置
int count = 0; // 记录是否包含所有字符
for(;r < size_s;++r) {
if (unordered_map_char_to_int[s[r]]-- > 0) {
++count;
while (count == size_t) { // 窗口内包含t的所有字符
if (r - l + 1 < min_size) {
min_l = l;
min_size = r - l + 1;
}
if (++unordered_map_char_to_int[s[l]] > 0) {
--count;
}
++l;
}
}
}
return min_size > size_s ? "" : s.substr(min_l, min_size);
}
};
考虑
-
如何记录窗口中新加入的元素？
根据题目，当窗口合法时，窗口内的子串应该包含所有t内的字符，因此只有新元素是在t中的字符才需要记录
-
一种思路是：每次加入新字符就在t中搜索一下是否存在，如果存在则需要记录
时间复杂度高
-
另一种思路是：用一个哈希表记录t中有哪些元素，利用哈希的key值来判断
只需初始化一次，时间复杂度更好；
注意这里哈希表实际上利用的是key值，对于value的值并没有限制，所以需要根据实际需要设置
-
-
如何判断窗口合法？
因为这题是求最小长度，所以一旦窗口合法就需要记录；
如果是求最长连续子串，应该是一旦窗口不合法就需要记录；
根据题目，要求最小长度的子串，所以一旦窗口覆盖所有t中字符，则说明窗口合法了，因此我们需要记录是否窗口内包含t中的所有字符
-
当窗口合法时，应该是窗口刚好保存所有t中所有字符的情况，但是如何判断是否窗口内的拥有的字符数量和t中对应的数量相等呢？
-
根据1中的哈希表，可以考虑在初始化时利用value记录t中每个元素的数量
然后在每次加入一个t中字符时，就将对应数量减1。因为允许窗口内该元素数量比t中多，所以哈希表的value值允许<0
-
但是，我们无法通过哈希表来判断是否窗口合法
如果利用哈希表判断，则应该是最后一个value=0时，说明窗口合法；也就是说，每当一个value=0时，都需要判断是否其他的value=0，比较麻烦
-
因为，只有value>0时，加入的元素才是真正有效的（如果<0，则说明这种字符已经比t中多了）；
所以，我们可以利用一个计数器count，当value>0时就加1，<0时就不变(因为实际上是不需要的)；
这样当count==t.size()时，说明t中所有元素都加入，此时刚好就是合法的时候
-
-
如何在移动窗口左边界时，判断移动后的窗口是否合法
- 因为左侧移动窗口左边界时，会将一个字符移出
- 当窗口不合法时，应该是因为字符该移出，导致窗口内的这种字符数量小于t中要求的数量
- 但是，注意的是，一个字符可能有多个元素，移出某个字符，并不代表将该字符的元素就一定小于t中要求的元素，所以我们应该需要记录窗口中某个字符的元素的数量，据该字符移除的元素的数量来判断来
所以，我们需要记录窗口内某种字符元素个数
-
根据1采用的哈希表，我们可以通过哈希表的value值来保存某个字符在窗口内的个数
正好也符合2的分析
-
根据2，我们知道value的值是在减小的，value<0的时候说明该字符的类型多于t中字符；
当移出一个元素时，可以将value反向操作，即加1，当value>0时，说明窗口不合法了，于是可以开始移动窗口右边界
