发布于个人公众号，打开微信，搜索
MelodyJerry即可
76. 最小覆盖子串
| 难度 | 困难 | 通过率 | 42.07% (161514/383873) |
|---|
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。
如果s中存在这样的子串，我们保证它是唯一的答案。
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC"
输出："BANC"
示例 2：
输入：s = "a", t = "a"
输出："a"
示例 3:
输入: s = "a", t = "aa"
输出: ""
解释: t 中两个字符 'a' 均应包含在 s 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
- 1 <=
s.length,t.length<= 105 -
s和t由英文字母组成
进阶：
你能设计一个在 o(n) 时间内解决此问题的算法吗？
题解
滑动窗口
在jerry之前的算法题解中，也是有过滑动窗口解法的题目。
-
滑动窗口，是一种框架思维：- 用
l,r表示滑动窗口的左边界和右边界，通过改变l,r来扩展和收缩滑动窗口
- 用
- 在这题目中可以想象成一个窗口在字符串上游走，当这个窗口包含的元素满足条件，即包含字符串
t的所有元素，记录下这个滑动窗口的大小slze = r-l+1，这些长度中的最小值就是要求的结果。 - 主要分以下几个步骤：
- 从0开始，不断增加
r使滑动窗口增大，直到窗口包含了t的所有元素 - 从0开始，不断增加
l使滑动窗口缩小，因为是要求最小字串，所以将不必要的元素排除在外，使长度减小，直到碰到一个必须包含的元素，这个时候不能再扔了，再扔就不满足条件了，记录此时滑动窗口的大小，并保存最小值 mln - 让
l再增加一个位置，这个时候滑动窗口肯定不满足条件了，那么继续从步骤1开始执行，寻找新的满足条件的滑动窗口，如此反复，直到r超出了字符串S范围 - 判断滑动窗口是否
包含了t中的所有元素，这是将考虑的最关键的一部分！！！
- 这里使用一个字典来记录
t中的字符以及个数，还有所需个数 - 用
need[128]来记录t中字符，字符将以ASCII形式存储 - 用
needCount表示当前遍历下，满足t还需要的元素个数 -
need[97]=2表示t中需要2个字符a，needCount=3表示覆盖t还需要3个字符 - 每当遍历到
t中的字符，其对应的need[]应该-1 - 当
needCount==0时，则当前窗口覆盖了t中所有元素
- 其次关键是如何判断当前遍历的字符是不是
多余的字符？要是多余，就可以移除。
- 在这里，我对上面的字典
need[]多加一步操作 - 无论当前遍历字符在不在
t中，都要在need中-1 - 要是
多余字符，其对应的need[]一定是<0 - 这样的目的：利用
need[]的正负来区分字符是否多余的还是有用的
- 最后一点，无论
左边界还是右边界，在边界移动时候，要注意维护对应的参数。
时间复杂度： O ( n ) O(n) O(n)。左右指针各自扫一遍字符串
s，时间复杂度是 O ( n ) O(n) O(n)。空间复杂度： O ( n ) O(n) O(n)。只用到一个字典用于记录的数组，长度128。
class Solution {
public String minWindow(String s, String t) {
// l(left): 左边界
// r(right): 右边界
int l = 0, r = 0;
// size=r-l+1: 滑动窗口的大小，默认值Integer.MAX_VALUE方便值交换
int size = Integer.MAX_VALUE;
// needCount: 当前遍历下，满足t还需要的元素个数，默认值、最大值是t.length，为0时表示滑动窗口内容覆盖了t中所有元素
int needCount = t.length();
// start: 记录有效滑动窗口的起始位置(左边界)，方便后续查找对应的字串
int start = 0;
// 字典need: 记录滑动窗口中需要t中各个元素的数量
// ASCII方式存储 [A-Z]：65-90 [a-z]：97-122
// need[97]=2 表示t中需要2个a
// t中对应字符的need[]必须>=0
// 若need[]<0表示是个多余的字符
int[] need = new int[128];
// 根据t的内容，向字典need添加元素
for (int i = 0; i < t.length(); i++)
need[t.charAt(i)]++;
// 循环条件，右边界不能溢出
while (r < s.length()) {
// 获取当前遍历的元素字符
char c = s.charAt(r);
// 若当前遍历字符是t中的内容，needCount需要-1
if (need[c] > 0)
needCount--;
// 无论c在不在t中，都要在need中-1
// 目的：利用正负来区分字符是否多余的还是有用的
need[c]--;
// needCount==0表示当前窗口满足t中所有元素
if (needCount == 0) {
// 判断左边界是否可以收缩
// 如果l对应字符的need[]<0，表示是个多余的字符
while (l < r && need[s.charAt(l)] < 0) {
// 在need[]中维护更新这个字符
need[s.charAt(l)]++;
// 左边界向右移，移除这个多余字符
l++;
}
// 判断是否更新有效滑动窗口的大小
if (r - l + 1 < size) {
// 更新
size = r - l + 1;
// 记录有效滑动窗口的起始位置(左边界)，方便查找对应的字串
start = l;
}
// 左边界对应的字符计数需要+1
need[s.charAt(l)]++;
// 重新维护左边界
l++;
// 重新维护当前的needCount
needCount++;
}
// 右边界向右移，寻找下一满足条件的有效滑动窗口
r++;
}
return size == Integer.MAX_VALUE ? "" : s.substring(start, start + size);
}
}