08数组-滑动窗口、HashMap

LeetCode——76. 最小覆盖子串

给你一个字符串 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 <= 105

• s 和 t 由英文字母组成

分析：

1.从示例3来看，字符串t中包含的重复字符也需要被字符串s涵盖。从这点分析符合Map的结构。

2.最短子串的问题符合滑动窗口的特点。

3.窗口伸长的条件是包含t中所有字符，窗口收缩的条件是左指针字符数量超出t中含有的，或者左指针字符不在字符串t中。当窗口内对应字符恰好包含t所有字符的时候，窗口长度就是结果值。

class Solution {
    public String minWindow(String s, String t) {
        String res = "";
        // 定义Map，存储字符串t中各字符数量
        Map ht = new HashMap<>();
        char item;
        for (int i = 0; i < t.length(); i++) {
            item = t.charAt(i);
            ht.put(item, ht.getOrDefault(item, 0) + 1);
        }
​
        // 定义滑动窗口边界
        int l = 0;
​
        // 定义map，存储窗口内涵盖的字符串
        Map hs = new HashMap<>();
        int count = 0;
        int len = Integer.MAX_VALUE;
        for (int r = 0; r < s.length(); r++) {
            hs.put(s.charAt(r), hs.getOrDefault(s.charAt(r), 0) + 1);
            if (ht.containsKey(s.charAt(r))) {
                if (hs.get(s.charAt(r)) <= ht.get(s.charAt(r))){
                    count ++;
                }
            }
            // 存在特殊情况-数组下标越界
            while (l ht.getOrDefault(s.charAt(l), 0)) {
                hs.put(s.charAt(l), hs.get(s.charAt(l)) - 1);
                l++;
                if(l>s.length() - 1){
                    break;
                }
            }
            if (count == t.length() && r-l+1 < len) {
                len = r - l + 1;
                res = s.substring(l, r+1);
            }
        }
​
        return res;
    }
}

• 时间复杂度：O(n)，滑动窗口双指针严格递增。

• 空间复杂度：O(C)，hashMap最多不会存放超过字符集大小的键值对，假设字符集大小为C。