大家好！我是曾续缘😘
今天是《LeetCode 热题 100》系列
发车第 12 天
子串第 3 题
❤️点赞 👍 收藏 ⭐再看，养成习惯

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
如果 s 中存在这样的子串，我们保证它是唯一的答案。
示例 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 的子串中，
因此没有符合条件的子字符串，返回空字符串。
提示：
^{m == s.length}
^{n == t.length}
1 <= m, n <= 10⁵
s 和 t 由英文字母组成
进阶：你能设计一个在 o(m+n) 时间内解决此问题的算法吗？
难度：💝💝💝

解题方法

这道题可以使用滑动窗口的方法来解决。

使用两个数组 chars 和 nums 来分别记录字符串 t 中包含的字符和每个字符的数量。
初始化变量 cnt 记录当前窗口中已经包含了多少个 t 中的字符，以及 l、min_l 和 min_size 分别记录窗口的左边界、最小子串的起始位置和长度。
遍历字符串 s，当遇到 t 中的字符时，将该字符数量减一，并更新 cnt。同时，在 cnt 等于 t 的长度时，说明当前窗口已经包含了 t 中所有字符，开始收缩窗口。
在收缩窗口时，更新最小子串的起始位置和长度，并移动左边界 l 直到不再满足条件。
最终返回最小子串或空字符串。

Code

查看代码

java

class Solution {
    public String minWindow(String s, String t) {
        boolean[] chars = new boolean[128];
        int[] nums = new int[128];
        for(int i = 0; i < t.length(); i++){
            chars[t.charAt(i)] = true;
            nums[t.charAt(i)]++;
        }
        int cnt = 0, l = 0, min_l = 0, min_size = s.length() + 1;
        for(int r = 0; r < s.length(); r++){
            if(chars[s.charAt(r)]){
                nums[s.charAt(r)]--;
                if(nums[s.charAt(r)] >= 0){
                    cnt++;
                }
            }
            while(cnt == t.length()){
                if(r - l + 1 < min_size){
                    min_l = l;
                    min_size = r - l + 1;
                }
                nums[s.charAt(l)]++;
                if(chars[s.charAt(l)] && nums[s.charAt(l)] > 0){
                    cnt--;
                }
                l++;
            }
        }
        return min_size <= s.length() ? s.substring(min_l, min_l + min_size) : "";
    }
}

解题方法 ​

Code ​

解题方法

Code