【滑动窗口】变种题目：leetcode76：最小覆盖子串
前言
滑动窗口是算法的数组部分中非常重要的一个内容，关于滑动窗口的题目，我已经发布过相关的变种题目文章，链接如下，欢迎访问：
如果你不了解什么是滑动窗口，推荐观看代码随想录的基础讲解视频：
了解完这些，我们便可以开始思考本题了。
题干
题目难度：困难
题目分析
题目给了2个字符串，分别是s和t，我们要在s中找到涵盖t中所有字符的子串。
注意题目中的涵盖，并不意味着两个字符串要长得一模一样，完全匹配，而是其中包含了t存在的所有字符。
通俗来讲就是，假如t中有a、b、c三个字符，数量分别为2，3，1，那么s的子串中一定要包含2个a，3个b，1个c。
根据这个思路，我们开始分析代码要怎么写。
同样的滑动窗口的方法，一个指针进行遍历，同时统计当前的子串，当它达到涵盖t的标准后，左指针再移动，缩小范围，同时更新子串，直到不符合条件，这时候右指针再继续遍历。
大致思路有了，我们要进一步思考，什么才是代表着子串涵盖t。
已知匹配并不是长得完全一样，通过字符串来存储匹配的方法是不合理的。
并且它们的字符的顺序也可以不相同，比如t是abbc，s的子串可以是babc。
s的子串里还可以包含不存在于t中的字符，比如s是babec。
这种情况下，我们不应该用字符串来进行比对，经过思考，我认为能够存储字符和字符的数量的最好的方式就是用Map的键值对存储。
key来存储字符，value存储它出现的次数。
通过创建map实例target，将t中所有字符和它出现的数量进行存储，这样遍历一遍t后，我们就得到了t的所有信息。
那么我们该怎么用s来和它比对呢？
首先我们要知道，t中一共有多少个字符，也就是target.size()，可以得到字符的数量。
设立一个变量valid，记录窗口中字符达到标准的字符数量。（达到标准指的是它的数量等于或大于t中本字符出现的数量）
右指针遍历s，当遍历的字符在t中存在的时候，我们将这个字符存储在记录窗口字符情况的Map集合window里。当window存储的这个字符数量达到了target中存储的本字符的数量，valid++;
当valid等于target.size()时，证明此时右指针已经挪动到了符合涵盖t字符的位置，这个时候可以开始移动左指针缩小窗口了，每次缩小都要保存当前的子串，当缩小到valid不符合条件的时候（某个字符数量不达标时），退出循环。
然后right继续移动，直到valid再次达标，这时候再继续缩小窗口，移动左指针… …
代码编写
题目的思路我们已经分析完了，接下来我们要开始代码的编写。
首先，我们要考虑题目的情况，找到s中涵盖t字符的子串，所以意味着s的长度得大于等于t，并且s和t不能够为空
if (s == null || t == null || s.length() < t.length()) {
return "";
}
这样，所有不符合条件的情况已经被排除了，接下来进入到查找子串的环节。
为了方便存储，可以将s和t转化成为数组
char[] chars=s.toCharArray();
char[] chart=t.toCharArray();
按照分析出的思路，将t中所有的字符，和每个字符出现的数量存储在Map集合里。
Map<Character, Integer> target = new HashMap<>();//存储t的字符和数量
for (char c : chart) {
target.put(c,target.getOrDefault(c,0)+1);
}
接着，我们需要另一个Map集合存储滑动窗口的字符和数量(只存储匹配t中字符成功的，没匹配上的不存储，直接跳过就行）
Map<Character, Integer> window = new HashMap<>();//存储s窗口的字符和数量
定义valid、left、right分别记录符合条件的字符数量和左右指针。
定义len存储子串的长度，方便进行匹配更新
定义start存储子串的起点，只有当len变小的时候才更新
完整代码
根据思路，完整代码如下：
class Solution {
public String minWindow(String s, String t) {
//如果s或t为空，直接返回
if (s == null || t == null || s.length() < t.length()) {
return "";
}
//转化字符串为数组
char[] chars=s.toCharArray();
char[] chart=t.toCharArray();
Map<Character, Integer> target = new HashMap<>();//存储t的字符和数量
for (char c : chart) {
target.put(c,target.getOrDefault(c,0)+1);
}
Map<Character, Integer> window = new HashMap<>();//存储s窗口的字符和数量
int valid=0; //记录当前窗口中包含多少个t中的字符
int left=0; //子串左边界
int right=0; //子串右边界
int len=chars.length+1;
int start=0; //最小子串起点
while (right < s.length()) {
char c = chars[right];
//扩展窗口，增加右侧字符的计数
if (target.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).intValue() == target.get(c).intValue()) {
valid++;
}
}
right++;
//判断窗口是否包含t中所有字符
while (valid == target.size()) {
//更新最小子串
if ((right - left) < len) {
len=right-left;
start = left;
}
char d = chars[left];
if (target.containsKey(d)) {
if (window.get(d).intValue() == target.get(d).intValue()) {
valid--;
}
window.put(d, window.get(d) - 1);
}
left++;
}
}
//substring(beginIndex,endIndex)的意思是从beginIndex到endIndex之前结束，不包括endIndex
return len==chars.length+1? "":s.substring(start,start+len);
}
}
原文地址：https://blog.csdn.net/weixin_47510148/article/details/143983137
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！