Q13 LeetCode76 最小覆盖子串

1.难题

2.need.containsKey(r) 看hashmap中是否含有r

3.明天再复盘一遍

 1 class Solution {
 2     public String minWindow(String s, String t) {
 3         if (s == null || s.isEmpty() || t == null || t.isEmpty() || s.length() < t.length()) return "";
 4 
 5         Map<Character, Integer> need = new HashMap<>();
 6         Map<Character, Integer> window = new HashMap<>();
 7 
 8         // 初始化 need，记录 t 中每个字符的出现次数
 9         for (char c : t.toCharArray()) need.put(c, need.getOrDefault(c, 0) + 1);
10 
11         int left = 0, right = 0; // 窗口的左右边界
12         int valid = 0; // 已经匹配上的字符数量
13         int start = 0, minLen = Integer.MAX_VALUE; // 最小窗口的起始位置和长度
14 
15         while (right < s.length()) {
16             char r = s.charAt(right);
17             right++;
18 
19             // 更新窗口内字符的计数
20             if (need.containsKey(r)) {
21                 window.put(r, window.getOrDefault(r, 0) + 1);
22                 if (window.get(r).equals(need.get(r))) valid++;
23             }
24 
25             // 当窗口内的字符已经完全包含了 t 中的所有字符时
26             while (valid == need.size()) {
27                 // 更新最小窗口的起始位置和长度
28                 if (right - left < minLen) {
29                     start = left;
30                     minLen = right - left;
31                 }
32 
33                 char l = s.charAt(left);
34                 // 缩小窗口，移动左边界
35                 if (need.containsKey(l)) {
36                     window.put(l, window.get(l) - 1);
37                     if (window.get(l) < need.get(l)) valid--;
38                 }
39                 left++;
40             }
41         }
42         return minLen == Integer.MAX_VALUE ? "" : s.substring(start, start + minLen);
43     }
44 }