算法016——最小覆盖子串
力扣——最小覆盖子串(点击跳转)
分析题目
我们先随便从一个位置开始,让 right 右移,直到找到符合题目的位置停下
之后,让 left 右移,此时会出现两种情况
- 仍然符合要求,right 不需要动
- 不符合要求,此时让 right 右移,知道找到符合要求的位置
所以我们使用滑动窗口 + 哈希表的方式来解决此问题。
此时,窗口满足出窗口,让 left 右移
- left = 0,right = 0
- 进窗口: hash2[in]++
- 判断:check(hash1,hash2)
更新结果:起始位置,最短长度
出窗口:hash2[out]–
跟上两篇博客一样,我们可以对判断条件做出优化
前两篇博客找到字符串中所有的字母异位词
定义一个变量 count 表示有效字符的种类
进窗口,要在相等的时候比较,相等说明此时进窗口的字符为有效字符,之后让 count++,如果按照上一道题,大于等于来比较的话,会有重复
出窗口时,加入 left 与 right 在如图所示的位置上,我们要在出窗口之前判断,等于说明出窗口的为有效字符,让 count–
最后判断 count 是否等于 hash1的长度
- 进窗口:hash2[in] == hash1[in] ——> count++
- 出窗口:hash2[out] == hash1[out] ——> count–
- 判断条件: count == hash1.size()
代码如下:
class Solution {
public String minWindow(String s, String t) {
char[] s1 = s.toCharArray();
char[] t1 = t.toCharArray();
int[] hash1 = new int[128];
int kind = 0;//用于统计 t 字符串中的字符种类的个数
for(char ch : t1){
if(hash1[ch]++ == 0){
kind++;
}
}
int[] hash2 = new int[128];
int minlen = Integer.MAX_VALUE;
int begin = -1;
for(int left = 0,right = 0,count = 0;right < s1.length;right++){
char in = s1[right];
if(++hash2[in] == hash1[in]){
count++;
}
while(kind == count){
if(right - left + 1 < minlen){
begin = left;
minlen = right - left + 1;
}
char out = s1[left++];
if(hash2[out]-- == hash1[out]){
count--;
}
}
}
if(begin == -1){
return new String();
}else{
return s.substring(begin,begin + minlen);
}
}
}
完成了,我要累死了,休息