[76] 最小覆盖子串
https://leetcode-cn.com/problems/minimum-window-substring/description/
- algorithms
- Hard (40.57%)
- Likes: 1042
- Dislikes: -
- Total Accepted: 120.1K
- Total Submissions: 293.1K
- Testcase Example: ‘“ADOBECODEBANC”\n”ABC”‘
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:如果 s
中存在这样的子串,我们保证它是唯一的答案。
示例 1:
输入:s = "ADOBECODEBANC", t = "ABC" 输出:"BANC"
示例 2:
输入:s = "a", t = "a" 输出:"a"
提示:
1 <= s.length, t.length <= 105
s
和t
由英文字母组成
进阶:你能设计一个在
o(n)
时间内解决此问题的算法吗?
方法1: 双指针(滑动窗口)
思路:
- 通过设置左右两个指针(left<=right), 在两指针之间形成一个窗口, 每次仅仅移动一侧的指针.
- 当前窗口未包含t中所需的所有字符串, 则右侧指针右移, 左侧指针不动, 直至满足条件;
- 此时右侧指针保持不动, 左侧指针移动来获得能满足条件的最小滑动窗口
知道原理后, 需要解决的问题如下:
如何判断滑动窗口中是否包含t中全部字符
- 设置
flag
数组用来记录t中出现的字母 - 设置
chars
数组用来记录t中字母出现的次数, 也可当作滑动窗口中还需要相应字母的个数. (当个数为负值则代表该字母有多余) - 设置
count
变量来表示滑动窗口已包含t中字母的个数, 当count == t.size()
时表示当前窗口已包含t中所有字母, 这也是滑动窗口左侧下标右移的条件 flag
,chars
也可用hashtable
- 因为字母
z
对应的ASCII码是123
, 所以将数组长度设为123即可, 不过将其设置为2的整数幂128更好
- 设置
如何设置滑动窗口的移动
- 具体设置见代码注释
- 注意: 这里设置的滑动窗口的区间为
[left, right)
, 左闭右开, 所以区间长度为right - left + 1
class Solution {
public:
string minWindow(string s, string t) {
// chars 存储t中对应字母出现的次数
// flag 记录t中出现的字母
vector<int> chars(128, 0);
vector<bool> flag(128, false);
for(int i=0; i<t.size(); ++i){
flag[t[i]] = true;
++chars[t[i]];
}
int count=0, left=0, min_left = 0, min_size = s.size() + 1;
// count 代表滑动窗口中已包含t中字符的个数
// min_left用于记录最小滑动窗口的左侧下标
// min_size 用于记录最小滑动窗口大小
for(int right=0; right<s.size(); ++right ){
if(flag[s[right]]){
if(--chars[s[right]]>=0){
++count;
}
while(count==t.size()){
// 更新最小滑动窗口
if(right - left + 1 < min_size){
min_left = left;
min_size = right -left + 1;
}
// 若左边待滑动元素是t中元素,并且若滑动, 当前滑动窗口不再包含t中所有字符
// 待滑动
if(flag[s[left]] && ++chars[s[left]] > 0){
--count;
}
// 执行滑动
//左侧向右滑动
++left;
}
}
}
return min_size > s.size() ? "" : s.substr(min_left, min_size);
}
};
复杂度分析:
- 时间复杂度:
O(n)
, 注意这里虽然for
循环里面有一个while
,但while
循环只负责left
指针的移动, 且left
指针只会从左向右移动1次, 故总的时间复杂度还是O(n)
- 空间复杂度:
O(1)