76 最小覆盖子串
又是子串,我们立即想到使用滑动窗口
思路
- 首先想到的肯定是暴力解法:暴力枚举 + 哈希表
- 然后在分析的过程中,发现双指针同向不回退,就可以利用这个单调性,联想到滑动窗口解法:滑动窗口 + 哈希表
解题方法
- 先创建两个哈希表,用来统计两个字符串中字符出现的次数
- 再将要覆盖的字符串t,存入哈希表baseHash
- 设置pos和minLen,用来记录子串的初始位置和最小长度(这步很关键,我们可以等循环结束再拷贝子串,而不是循环中,减少了很多时间开销)
- 其次设置count,用来记录curHash中的有效字符个数(这步优化,可以让我们不用每次都一一比较两个哈希表,而是比较count是否达到t的有效字符个数)
接下来,是正常的滑动窗口四步走(详见代码):
- 进窗口
- 判断
- 出窗口
- 处理结果(这步的位置根据题目要求而变化)
复杂度
- 时间复杂度:O(m+n)
- 空间复杂度:O(1)
class Solution {
public:
string minWindow(string s, string t) {
unordered_map<char, int> window, need;
// 记录t的字符个数
for(char c : t){
need[c]++;
}
int left = 0, right = 0;
// valid记录满足的字符个数
int valid = 0;
int start = 0, len = INT_MAX;
while(right < s.size()){
char c = s[right];
right++;
// 更新数据
if(need.count(c)){
window[c]++;
if(window[c] == need[c]){
valid++;
}
}
while(valid == need.size()){
if(right - left < len){
start = left;
len = right - left;
}
char d = s[left];
left++;
// 更新数据
if(need.count(d)){
if(window[d] == need[d]){
valid--;
}
window[d]--;
}
}
}
return len == INT_MAX ? "" : s.substr(start, len);
}
};