LeetCOde | 76 | 最小覆盖子串 | 双指针 | 滑动窗口 | 哈希集合

发表于 更新于 分类于 ， ， 阅读次数： 阅读次数： Waline： 本文字数： 5.6k 阅读时长 ≈ 9 分钟
这道题在LeetCode上的难度标签为：困难！你能看出来这是一道用双指针就可以解决的题目吗？
LeetCode链接：76. 最小覆盖子串

1.题目描述

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

注意：

  • 对于 t 中重复字符，我们寻找的子字符串中该字符数量必须不少于 t 中该字符数量。
  • 如果 s 中存在这样的子串，我们保证它是唯一的答案。

示例 1：

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

示例 2：

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

示例 3:

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

提示：

  • m == s.length
  • n == t.length
  • $1 <= m, n <= 10^5$
  • s 和 t 由英文字母组成

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

2.题解

2.1 暴力解法(超时)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        // 创建Map集合用于记录t字符串中的字母及其个数
        Map<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            map.put(c, map.getOrDefault(c, 0) + 1);
        }

        // 初始化最小长度为一个较大的值
        int minLen = Integer.MAX_VALUE;
        // 初始化左右指针
        int left = 0, right = 0;
        // 用于记录当前窗口的长度
        int length = 0;
        // 用于记录最终结果的子串
        String result = "";

        // 遍历s字符串
        for (left = 0; left < s.length(); left++) {
            // 每次左指针移动时都重新创建一个countMap，复制map
            Map<Character, Integer> countMap = new HashMap<>(map);

            // 从当前left位置开始移动右指针
            for (right = left; right < s.length(); right++) {
                char c = s.charAt(right);
                // 如果右指针位置的字符在countMap中，减少它的计数
                if (countMap.containsKey(c)) {
                    countMap.put(c, countMap.get(c) - 1);
                    // 如果计数减少到0，移除该字符
                    if (countMap.get(c) == 0) {
                        countMap.remove(c);
                    }
                }

                // 当countMap为空时，说明当前窗口包含了t中的所有字符
                if (countMap.size() == 0) {
                    // 计算当前窗口的长度
                    length = right - left + 1;
                    // 更新最小长度和结果字符串
                    if (length < minLen) {
                        minLen = length;
                        result = s.substring(left, right + 1);
                    }
                    break;
                }
            }
        }

        return result;
    }
}

2.2 双指针-哈希集合

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
import java.util.HashMap;
import java.util.Map;

class Solution {
    // 创建Map集合用于记录t字符串中的字母及其个数
    Map<Character, Integer> tMap = new HashMap<>();
    // 创建Map集合用于记录s字符串滑动窗口过程中的字母及其个数
    Map<Character, Integer> sMap = new HashMap<>();

    /**
     * 找到字符串s中包含字符串t所有字符的最小子串
     *
     * @param s 字符串s
     * @param t 字符串t
     * @return 包含字符串t所有字符的最小子串
     */
    public String minWindow(String s, String t) {
        // 初始化tMap，用于记录t字符串中的每个字符及其出现次数
        for (int i = 0; i < t.length(); i++) {
            Character c = t.charAt(i);
            tMap.put(c, tMap.getOrDefault(c, 0) + 1);
        }

        // 初始化最小长度和结果字符串
        int minLen = Integer.MAX_VALUE;
        String result = "";

        // 滑动窗口的左右指针
        int left, right;
        // 遍历s字符串
        for (left = 0, right = 0; right < s.length(); right++) {
            // 获取当前字符
            Character c = s.charAt(right);
            // 将当前字符加入sMap中，记录其出现次数
            sMap.put(c, sMap.getOrDefault(c, 0) + 1);

            // 当滑动窗口中包含t字符串的所有字符时，收缩左边界
            while (check()) {
                // 更新最小长度和结果字符串
                int length = right - left + 1;
                if (length < minLen) {
                    minLen = length;
                    result = s.substring(left, right + 1);
                }
                // 移除左边界的字符，并更新sMap中的计数
                c = s.charAt(left);
                sMap.put(c, sMap.get(c) - 1);
                // 收缩左边界
                left++;
            }
        }

        // 返回最小窗口的子串
        return result;
    }

    /**
     * 检查当前滑动窗口是否包含t字符串中的所有字符
     *
     * @return 如果包含所有字符，返回true；否则返回false
     */
    public boolean check() {
        // 遍历tMap中的每个字符及其计数
        for (Map.Entry<Character, Integer> entry : tMap.entrySet()) {
            Character c = entry.getKey();
            // 如果sMap中当前字符的计数小于tMap中的计数，返回false
            if (sMap.getOrDefault(c, 0) < entry.getValue()) {
                return false;
            }
        }
        // 如果sMap中包含tMap中的所有字符及其计数，返回true
        return true;
    }
}

2.3 双指针-哈希数组

  • 如果能用哈希集合，那么大概率也可以使用哈希数组
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
class Solution {
    // 主方法，寻找字符串 s 中包含字符串 t 的最小窗口子串
    public String minWindow(String s, String t) {
        // 用于存储 t 中各字符的出现次数
        int[] tArr = new int[128];
        // 用于存储 s 中当前窗口各字符的出现次数
        int[] sArr = new int[128];

        // 初始化 tArr 数组
        for (int i = 0; i < t.length(); i++) {
            tArr[t.charAt(i)]++;
        }

        int left = 0, right = 0; // 左右指针初始化为 0
        int minLen = Integer.MAX_VALUE; // 最小长度初始化为无穷大
        String result = ""; // 最终结果字符串初始化为空

        // 移动右指针，扩展窗口
        while (right < s.length()) {
            sArr[s.charAt(right)]++; // 记录右指针指向字符的出现次数
            // 当窗口内的字符已经包含 t 中所有字符时，移动左指针缩小窗口
            while (check(sArr, tArr)) {
                int length = right - left + 1; // 计算当前窗口长度
                if (length < minLen) { // 如果当前窗口长度小于最小长度，更新最小长度和结果字符串
                    minLen = length;
                    result = s.substring(left, right + 1);
                }
                sArr[s.charAt(left)]--; // 左指针右移前，减少左指针指向字符的出现次数
                left++; // 左指针右移，缩小窗口
            }
            right++; // 右指针右移，扩大窗口
        }
        return result; // 返回结果字符串
    }

    // 检查当前窗口是否包含 t 中所有字符
    public boolean check(int[] sArr, int[] tArr) {
        // 检查大写字母 A-Z
        for (int i = 'A'; i <= 'Z'; i++) {
            if (sArr[i] < tArr[i]) {
                return false;
            }
        }
        // 检查小写字母 a-z
        for (int i = 'a'; i <= 'z'; i++) {
            if (sArr[i] < tArr[i]) {
                return false;
            }
        }
        return true; // 当前窗口包含 t 中所有字符
    }
}

2.4 优化

  • 上面两种方法，每次都需要调用check()函数，我们能不能优化一下呢？
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
    // 主方法，寻找字符串 s 中包含字符串 t 的最小窗口子串
    public String minWindow(String s, String t) {
        // 用于存储 t 中各字符的出现次数
        int[] tArr = new int[128];
        // 用于存储 s 中当前窗口各字符的出现次数
        int[] sArr = new int[128];

        // 初始化 tArr 数组，记录 t 中每个字符的出现次数，并统计不同字符的种类数
        int cnt = 0;
        for (int i = 0; i < t.length(); i++) {
            if (tArr[t.charAt(i)]++ == 0) {
                cnt++;
            }
        }

        int left = 0, right = 0; // 左右指针初始化为 0
        int minLen = Integer.MAX_VALUE; // 最小长度初始化为无穷大
        String result = ""; // 最终结果字符串初始化为空

        // 移动右指针，扩展窗口
        while (right < s.length()) {
            char c = s.charAt(right);
            sArr[c]++;
            // 当窗口中的某字符数量达到 t 中该字符的数量时，计数器 cnt 减 1
            if (sArr[c] == tArr[c]) {
                cnt--;
            }
            
            // 当计数器 cnt 为 0 时，窗口包含了 t 中所有字符
            while (cnt == 0) {
                int length = right - left + 1;
                // 更新最小长度和结果子字符串
                if (length < minLen) {
                    minLen = length;
                    result = s.substring(left, right + 1);
                }
                // 移动左指针，缩小窗口
                char x = s.charAt(left);
                sArr[x]--;
                // 当某字符数量小于 t 中该字符数量时，计数器 cnt 加 1
                if (sArr[x] < tArr[x]) {
                    cnt++;
                }
                left++;
            }
            right++;
        }
        return result; // 返回结果字符串
    }
}
-------------本文结束感谢您的阅读-------------