LeetCode.H76.最小覆盖子串

LeetCode.H76

题目：

题目大意：

如图所示。

数据范围：

如图所示
1

思路：

滑动窗口 (j, i)：使用滑动窗口的必要条件为，当枚举的 i 点向后移动时，j 只能向后移动，而不能向前移动。

我们每次向后移动一位 i ，再向后移动 j ，同时维护 1.hs：记录窗口中的各个元素的个数的哈希表，2.cnt：记录窗口中属于 t 中元素的总个数（当 cnt == t.lenght() 的时候，及为一个合法答案）。初始时我们用哈希表 ht 记录一下 t 中每个元素的个数。

在向后移动一位 i 时，更新 hs[si] 的值，如果满足条件1，则 cnt ++ 。然后向后移动 j ，在移动 j 时，如果满足条件2，则可以向后移动 j。直到不满足为止。

• 条件1：对于增加si，当 hs[si] <= ht[si] 的时候，说明在该窗口中 si 的个数小于等于 t 中该元素的个数，则可以 cnt ++ 。
• 条件2：对于删除sj：当 hs[sj] > ht[sj] 的时候，说明在该窗口中 sj 的个数已经大于了 t 中该元素的个数，则可以删除该 sj （即可以向后移动 j）。

如果 cnt == t.length() 则找到了一个s的一个包含 t 中所有元素的子串，并更新答案。

代码：

import java.util.HashMap;
import java.util.Map;

class Solution {
    public String minWindow(String s, String t) {
        Map<Character, Integer> ht = new HashMap<>();
        for (int i = 0; i < t.length(); i ++ ){
            ht.put(t.charAt(i), ht.getOrDefault(t.charAt(i), 0) + 1);
        }
        String res = "";
        int cnt = 0;
        Map<Character, Integer> hs = new HashMap<>();
        for (int i = 0, j = 0; i < s.length(); i ++ ){
            hs.put(s.charAt(i), hs.getOrDefault(s.charAt(i), 0) + 1);
            if (hs.get(s.charAt(i)) <= ht.getOrDefault(s.charAt(i), 0))
                cnt ++ ;
            while (j < i && hs.get(s.charAt(j)) > ht.getOrDefault(s.charAt(j), 0)){
                hs.put(s.charAt(j),hs.get(s.charAt(j)) - 1);
                j ++ ;
            }
            if (cnt == t.length()){
                String sub = s.substring(j, i + 1);
                if (res.equals("") || res.length() > sub.length()){
                    res = sub;
                }
            }
        }
        return res;
    }
}

public class Main {
    public static void main(String[] args) {
        Solution solution = new Solution();
        String s = "a", t = "b";
        System.out.println(solution.minWindow(s, t));
    }
}

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

时空复杂度分析等：

• 时间复杂度 : O(n)

• 空间复杂度 : O(n)

题目链接：

76. 最小覆盖子串 - 力扣（LeetCode）