给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
注意:
- 对于
t
中重复字符,我们寻找的子字符串中该字符数量必须不少于t
中该字符数量。 - 如果
s
中存在这样的子串,我们保证它是唯一的答案。
提示:
1 <= s.length, t.length <= 105
-
s
和t
由英文字母组成
解题思路:双指针+滑动窗口
滑动窗口的思想:
用i,j表示滑动窗口的左边界和右边界,通过改变l,r来扩展和收缩滑动窗口,可以想象成一个窗口在字符串上游走,当这个窗口包含的元素满足条件,即包含字符串 T 的所有元素,记录下这个滑动窗口的长度 r - l + 1,这些长度中的最小值就是要求的结果。
步骤一
不断增加j使滑动窗口增大,直到窗口包含了 T 的所有元素
步骤二
不断增加i使滑动窗口缩小,因为是要求最小字串,所以将不必要的元素排除在外,使长度减小,直到碰到一个必须包含的元素,这个时候不能再扔了,再扔就不满足条件了,记录此时滑动窗口的长度,并保存最小值
步骤三
让 l 再增加一个位置,这个时候滑动窗口肯定不满足条件了,那么继续从步骤一开始执行,寻找新的满足条件的滑动窗口,如此反复,直到j超出了字符串S范围。
面临的问题:
如何判断滑动窗口包含了T的所有元素?
我们用一个数组res(或者使用map来进行存储)来表示当前滑动窗口中需要的各元素的数量,一开始滑动窗口为空,用 T 中各元素来初始化这个res,当滑动窗口扩展或者收缩的时候,去维护这个 res 数组,例如当滑动窗口包含某个元素,我们就让 res 中这个元素的数量减 1,代表所需元素减少了1个;当滑动窗口移除某个元素,就让 res 中这个元素的数量加1。
记住一点:res 始终记录着当前滑动窗口下,我们还需要的元素数量,我们在改变 l , r 时,需同步维护 res。
值得注意的是,只要某个元素包含在滑动窗口中,我们就会在 res 中存储这个元素的数量,如果某个元素存储的是负数代表这个元素是多余的。比如当 res 等于{'A':-2,'C':1}时,表示当前滑动窗口中,我们有 2 个A是多余的,同时还需要 1 个C。这么做的目的就是为了步骤二中,排除不必要的元素,数量为负的就是不必要的元素,而数量为 0 表示刚刚好。
回到问题中来,那么如何判断滑动窗口包含了T的所有元素?结论就是当 res 中所有元素的数量都小于等于 0 时,表示当前滑动窗口不再需要任何元素。
优化
如果每次判断滑动窗口是否包含了T的所有元素,都去遍历 res 看是否所有元素数量都小于等于0,这个会耗费O(k)的时间复杂度,k 代表数组长度,最坏情况下,k 可能等于len(S)。
其实这个是可以避免的,我们可以维护一个额外的变量 count 来记录所需元素的总数量,当我们碰到一个所需元素c,不仅res[c]的数量减少1,同时 count 也要减少1,这样我们通过 count 就可以知道是否满足条件,而无需遍历数组了。
前面也提到过,res 记录了遍历到的所有元素,而只有res[c] > 0大于0时,代表c就是所需元素
代码和提交截图如下:
class Solution {
public String minWindow(String s, String t) {
if(s.length() == 0 || t.length() == 0 || s.length() < t.length()){
return "";
}
int[] res = new int[58];
//记录需要的字符的个数
for(int i = 0 ; i < t.length() ; i++){
res[t.charAt(i)-'A']++;
}
//l是当前左边界,r是当前右边界,size记录窗口大小,count是需求的字符个数,startIndex是最小覆盖串开始的index
int count = t.length();
int l = 0 ;
int r = 0 ;
int startIndex = 0;
int size = Integer.MAX_VALUE;
//遍历所有字符
while(r < s.length()){
char temp = s.charAt(r);
//如果 temp-'A' > 0,则说明temp是需要的字母,count--。
if(res[temp-'A'] > 0){
count--;
}
res[temp-'A']--;
//count == 0 说明 l 和 r 之间的区域已经包含了t的所有字母,这时候需要优化 l 指针。
if(count == 0){
while(l < r && res[s.charAt(l) - 'A'] < 0){
res[s.charAt(l) - 'A']++;
l++;
}
//l指针也已经优化到了最好,这时候就要判断当前这一段的长度和之前比有没有短,短则记录。
if(r-l+1 < size){
size = r-l+1;
startIndex = l;
}
//完事之后将l++;打破 count 的平衡。
res[s.charAt(l) - 'A']++;
l++;
count++;
}
r++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(startIndex,startIndex+size);
}
}
总结:这道题是上次没有 ac 的一道题,起初我用的是暴力的方法,将数组中所有大于等于t长度的子串全都模拟一遍,并且计算是不是包括,但是有个测试用例超时了。