蓝桥杯入门即劝退（十八）最小覆盖子串（滑动窗口解法）

小咪咪 2023-09-24 19:40 41阅读 0赞

**欢迎===关注===点赞===评论，共同学习，共同进步！**

\------持续更新蓝桥杯入门系列算法实例--------

如果你也喜欢Java和算法，欢迎订阅专栏共同学习交流！

你的点赞、关注、评论、是我创作的动力！

**-------希望我的文章对你有所帮助--------**

**前言：****过年前后因为个人原因没有持续更新，目前已经开学，将会稳定更新各种算法题解，4月份即是蓝桥杯竞赛了，时不我待，共同加油进步！趁着我们年轻且充满希望，努力吧！**

## 一、题目描述 ##

给你一个字符串 `s` 、一个字符串 `t` 。返回 `s` 中涵盖 `t` 所有字符的最小子串。如果 `s` 中不存在涵盖 `t` 所有字符的子串，则返回空字符串 `""` 。

**示例 1：**

>     输入：s = "ADOBECODEBANC", t = "ABC"
>     输出："BANC"
>     解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。

**示例 2：**

>     输入：s = "a", t = "a"
>     输出："a"
>     解释：整个字符串 s 是最小覆盖子串。

**示例 3:**

>     输入: s = "a", t = "aa"
>     输出: ""
>     解释: t 中两个字符 'a' 均应包含在 s 的子串中，
>     因此没有符合条件的子字符串，返回空字符串。

## 二、思路及题解 ##

> 这题是力扣上的hard难度，本人自己写的算法在最后一个测试用例无法通过，显然是时间复杂度过高导致的超时，于是便参考其他大佬的方法重新写了一个，接下来讲讲我的思路。
> 
> **1、本题是两个字符串进行匹配重复子串问题，首先把两个字符串转化为字符数组，toCharArray（）即可实现。**
> 
> **2、使用HashMap哈希表来统计每个字符出现的次数。**
> 
> **3、确定一个区间为\[left,right）的滑动窗口，首先将字符数组t放入Target中，如果匹配到相同的字母即将该字母添加到Window（滑动窗口）中，即right++，窗口扩张的过程。**
> 
> **4、遍历后当滑动窗口中国的字母数量Valid与Target一致时，即是符合条件的子串，记录长度Len。**
> 
> **5、窗口开始移动，left++，将首个字母进行剔除，再次验证窗口是否符合条件，不符合则Vaild-1。**
> 
> **6、直至再次母数量Valid与Target一致时进行子串长度比较，最后窗口right触及边界则获得最短的子串。**

## 三、参考代码 ##

>     public String minWindow(String s, String t) {
>             char[] T = t.toCharArray();
>             char[] S = s.toCharArray();
>             Map<Character, Integer> Window = new HashMap<>();
>             Map<Character, Integer> Target = new HashMap<>();//匹配目标
>             int left = 0, right = 0, start = 0;
>             int Valid = 0, Len = Integer.MAX_VALUE;//默认设为最大值
>     
>             for (char ch : T) Target.put(ch, Target.getOrDefault(ch, 0) + 1);//将t字符串放入哈希表
>             while (right < s.length()) {
>                 char ch = S[right];
>                 right++;
>                 if (Target.containsKey(ch)) {
>                     Window.put(ch, Window.getOrDefault(ch, 0) + 1);
>                     if (Target.get(ch).equals(Window.get(ch)))
>                         Valid++;//匹配到相同字母累加计算
>                 }
>                 while (Valid == Target.size()) {//当目标字母全部都包含在s中时
>                     if (right - left < Len) {
>                         start = left;
>                         Len = right - left;
>                     }
>                     char d = S[left];
>                     left++;//窗口左移，开始收缩
>                     if (Target.containsKey(d)) {
>                         Window.put(d, Window.get(d) - 1);
>                         if (Window.get(d) < Integer.valueOf(Target.get(d)))
>                         {
>                             Valid--;
>                         }
>                     }
>                 }
>             }
>             return Len == Integer.MAX_VALUE ? "" : s.substring(start, start + Len);
>         }

**发文不易，恳请大佬们高抬贵手！**

**点赞：随手点赞是种美德，是大佬们对于本人创作的认可！**

**评论：往来无白丁，是你我交流的的开始！**

**收藏：愿君多采撷，是大佬们对在下的赞赏！**