前言

滑动窗口是算法的数组部分中非常重要的一个内容，关于滑动窗口的题目，我已经发布过相关的变种题目文章，链接如下，欢迎访问：

【滑动窗口】相关题目分析讲解:leetcode209,leetcode904

如果你不了解什么是滑动窗口，推荐观看代码随想录的基础讲解视频：

拿下滑动窗口！ | LeetCode 209 长度最小的子数组

了解完这些，我们便可以开始思考本题了。

题干

题目难度：困难

题目分析

题目给了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之前结束，不包括endIndexreturn len==chars.length+1? "":s.substring(start,start+len);}
}