76. 最小覆盖子串

电玩女神 2022-10-13 01:55 190阅读 0赞

链接：[https://leetcode-cn.com/problems/minimum-window-substring/][https_leetcode-cn.com_problems_minimum-window-substring]

标签：**哈希表、字符串、滑动窗口**

> 题目

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

注意：如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

输入：s = "ADOBECODEBANC", t = "ABC"
    输出："BANC"

示例 2：

输入：s = "a", t = "a"
    输出："a"

提示：

*  1 <= s.length, t.length <= 105
 *  s 和 t 由英文字母组成

\*\*进阶：\*\*你能设计一个在 `o(n)` 时间内解决此问题的算法吗？

> 分析

如果要在O(n)时间内解决此题，那么循环肯定是不行的，所以此题使用**滑动窗口**来解决，也是双指针的一种题型。

思路就是：

（1）使用两个指针left、right，初始left = right = 0。\[left, right)称为一个窗口。

（2）right不断右移寻找目标字符放入**窗口序列**中，直到**窗口序列**全部包含目标字符。

（3）left右移，把字符从窗口序列中移除，直到窗口序列不包含目标子串，此时得到一个最短的目标子串。

（4）重复（2）（3）两步，不断更新最短目标子串，直到right到达字符串末尾。

其实第（2）步相当于找到了一个**可行解**，第（3）步就是找到一个**最优解**。

综上，我们需要用到的几个变量是：双指针left和right，窗口序列window，目标序列need，记录最短目标子串的长度。其他的按需增加。

> 编码

class Solution { 
        public String minWindow(String s, String t) { 
            // 目标字符数组
            Map<Character, Integer> need = new HashMap<>();
            // 窗口数组
            int[] window = new int[128];
            // valid已找到的字符数
            int left = 0, right = 0, valid = 0;
            // 最小子串的长度
            int len = Integer.MAX_VALUE;
            // 最小子串的起始下标
            int start = 0;
            for (int i = 0; i < t.length(); i++) { 
                need.put(t.charAt(i), need.getOrDefault(t.charAt(i), 0) + 1);
            }
    
            // 右指针往右走
            while (right < s.length()) { 
                char c = s.charAt(right);
                right++;
                // 说明这个字符包含在目标字符串中
                if (need.containsKey(c)) { 
                    window[c]++;
                    // 找到了一个满足条件的字符（数量够了）
                    if (window[c] == need.get(c)) { 
                        valid++;
                    }
                }
    
                // 所有的目标字符都已经找到，缩小窗口寻找最小子串
                while (valid == need.size()) { 
                    // 更新起始下标和最小子串的长度
                    if (right - left < len) { 
                        len = right - left;
                        start = left;
                    }
                    // 移出窗口的元素
                    char d = s.charAt(left);
                    left++;
                    if (need.containsKey(d)) { 
                        if (need.get(d) == window[d]) { 
                            valid--;
                        }
                        window[d]--;
                    }
                }
            }
    
            return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
        }
    }

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70]

[https_leetcode-cn.com_problems_minimum-window-substring]: https://leetcode-cn.com/problems/minimum-window-substring/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2FfaGVsbG93b3Jk_size_16_color_FFFFFF_t_70]: /images/20221005/092caf3298f646e0ac9d69e7f60b059d.png