题意
给你一个字符串 S、一个字符串 T 。请你设计一种算法，可以在 O(n) 的时间复杂度内，从字符串 S 里面找出：包含 T 所有字符的最小子串。
示例：
输入：S = "ADOBECODEBANC", T = "ABC"输出："BANC"
提示：
- 如果 S 中不存这样的子串，则返回空字符串 “”。
- 如果 S 中存在这样的子串，我们保证它是唯一的答案。
思路
显而易见这道题需要使用滑动窗口来解答，但是这道题比较难，我们不妨从最简单的地方想起：
首先，返回一个 window，至少要包含 target 中的所有的字符；
第二，在返回的 window，要尽可能地使得它最小。
接下来我们就来考虑如何实现上面两点：
第一，返回一个 window 至少要包含 T 中的所有字符
考虑到 T 中的 char 可能重复，所以实现应该用一个 hash 来存储 T 中的 String 的分布情况，代码中用到了int[] need = new int[128]；
接下来，比如在 eeaaaabbcd 中找寻 eec ，那么显然返回的最小窗口是 eeaaaabbc，在这个最小窗口中，need[e] = 2, need[c] = 1；
也就是说，如果当前找到了a, d等等不在 T 中的字符，虽然知道不会真正需要它们，但是也没法把它们去掉构成一个不连续的窗口，所以只能忽略不计继续扫下一个字符，而如果找到了下一个字符，并且下一个字符的数量还没到到 T 需要的数量，那么就应该接下往下找。
第二，在返回的 window，要尽可能地使得它最小。
我们可以用滑动窗口思想解决这个问题，在滑动窗口类型的问题中都会有两个指针。
- 一个用于“延伸”现有窗口的 right 指针
- 一个用于“收缩”现有窗口的 left 指针
在任一时刻，只有一个指针运动，而另一个保持静止。
我们在 s 上滑动窗口，通过移动 r 指针不断扩张窗口。当窗口包含 t 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。
代码
代码实现来自 LeetCode题解评论区。
Java代码实现：
class Solution {
public String minWindow(String s, String t) {
if (s == null || s == "" || t == null || s.length < t.length) {
return "";
}
//维护两个数组，记录已有字符串指定字符的出现次数，和目标字符串指定字符指定字符的出现次数
//ASCII表总长128
int[] need = new int[128];
int[] have = new int[128];
//将目标字符串指定字符的出现次数记录下来
for (int i = 0; i < t.length(); i++) {
nees[t.charAt(i)]++;
}
int len = s.length();
//分别为左指针，右指针，最小长度（初始值为一定不可达的长度）
//已有字符串中目标字符串指定字符的出现总频次以及最小覆盖子串在原字符串中的其起始位置
int left = 0, right = 0, min = s.length() + 1, count = 0, start = 0;
while (right < len) {
char r = s.charAt(right);
if (need[r] == 0) {
//说明该字符不被目标字符串需要，此时有两种情况：
// 1.循环刚开始，那么直接移动字右指针即可，不需要做多余的判断；
// 2.循环已经开始一段时间，此时又有两种情况：
// 2.1 上一次条件不满足，已有字符串指定字符出现次数不满足目标字符串指定字符出现次数，
// 那么此时如果该字符还不被目标字符串需要，就不需要进行多余判断，右指针移动即可。
// 2.2 左指针已经移动完毕，那么此时就相当于循环刚刚开始，同理直接移动右指针即可。
right++;
continue;
}
if (have[r] < need[r]) {
//当且仅当已有字符串目标字符出现的次数小于目标字符串字符的出现次数时，count才会+1
//是为了后续能直接判断已有字符串是否已经包含了目标字符串的所有字符，不需要挨个比对字符出现的次数
count++;
}
//已有字符串中目标字符出现的次数+1
have[r]++;
//移动右指针
right++;
//当且仅当已有字符串已经包含了所有目标字符串的字符，且出现频次大于或等于指定频次
while (count == t.length()) {
//当窗口的长度比已有的最小值还小时，更改最小值，并记录起始位置
if (right - left < min) {
min = right - left;
start = left;
}
char l = s.chatAt(left);
//如果左边即将要去掉的字符不被目标字符串需要，那么不需要做多余判断，直接可以移动左指针
if (need[l] == 0) {
left++;
continue;
}
//如果左边即将要去掉的字符串需要，且出现的频次正好等于指定频次，那么如果去掉这个字符，
//就不满足覆盖子串的条件，此时要破坏循环条件跳出循环，即控制目标字符串指定字符的出现总频次（count）-1
if (have[l] == need[l]) {
count--;
}
//已有字符串中目标字符出现的次数-1
have[l]--;
//移动左指针
left++;
}
}
//如果最小长度还为初始值，说明没有符合条件的子串
if (min == s.length() + 1) {
return "";
}
//返回的为以记录的起始位置为起点，记录的最短长度为距离的指定字符串中截取的子串
return s.substring(start, start + min);
}
}
上面代码的简略版本：
class Solution {
public String minWindow(String s, String t) {
int sLen = s.length();
int tLen = t.length();
// 特值判断
if (s == null || sLen == 0 || t == null || tLen == 0 || sLen < tLen) {
return "";
}
int[] have = new int[128];
int[] need = new int[128];
for (int i = 0; i < tLen; i++) {
need[t.charAt(i)]++;
}
int left = 0, right = 0, min = sLen + 1, count = 0, start = 0;
while (right < sLen) {
char r = s.charAt(right);
if (need[r] == 0) {
right++;
continue;
}
if (have[r] < need[r]) {
count++;
}
have[r]++;
right++;
while (count == tLen) {
if (right - left < min) {
min = right - left;
start = left;
}
char l = s.charAt(left);
if (need[l] == 0) {
left++;
continue;
}
if (have[l] == need[l]) {
count--;
}
have[l]--;
left++;
}
}
if (min == sLen + 1) {
return "";
}
return s.substring(start, start + min);
}
}
其实可以很粗暴的将大的while看成看成“延伸”阶段，然后将小的while看成比较以及“收缩阶段”。
若有收获，就点个赞吧
0 人点赞
