目录
题目
题目描述
给定两个字符串 s 和 t，请你在字符串 s 中找到包含 t 中所有字符的最小子串。
要求：
如果 s 中存在这样一个子串，返回这个最小子串。
如果不存在这样的子串，则返回空字符串 ""。
注意：
如果 s 中存在多个符合条件的子串，返回长度最小的那个。
t 中的字符可以在子串中以任何顺序出现，但每个字符的出现次数必须与 t 中相同或更多。
输入: s = "ADOBECODEBANC", t = "ABC"
输出: "BANC"
解释: "BANC" 是包含 "ABC" 的最小子串。
输入: s = "a", t = "a"
输出: "a"
解释: 子串 "a" 自身就是满足条件的最小窗口。
输入: s = "a", t = "aa"
输出: ""
解释: 因为 "a" 中只包含一个 "a"，不满足 "t" 中两个 "a" 的条件，因此返回空字符串。
约束条件
s 和 t 的长度均不会超过 10^5。
字符串 s 和 t 由英文字母组成。
解决思路
这道题可以使用滑动窗口的技巧来解决：
- 初始化：使用两个字典，一个存储目标字符串
t中各字符的计数，一个存储当前窗口中各字符的计数。 - 扩展窗口：使用右指针逐步扩展窗口，直到窗口包含了
t中所有字符。 - 缩小窗口：一旦窗口满足条件，使用左指针尝试缩小窗口以找到更小的符合条件的子串。
- 更新最优解：在每次找到符合条件的窗口时，更新当前最小的覆盖子串的长度及其位置。
- 返回结果：如果找到满足条件的子串，返回最小的那个；如果没有找到，返回空字符串。
代码
class Solution {
// 用于存储字符串 t 中每个字符及其出现的次数
Map<Character, Integer> ori = new HashMap<Character, Integer>();
// 用于存储当前窗口中对应字符的出现次数
Map<Character, Integer> cnt = new HashMap<Character, Integer>();
public String minWindow(String s, String t) {
int tLen = t.length();
// 初始化 ori 字典，存储 t 中每个字符出现的次数
for (int i = 0; i < tLen; i++) {
char c = t.charAt(i);
ori.put(c, ori.getOrDefault(c, 0) + 1);
}
// 定义双指针 l 和 r, l 是左边界，r 是右边界
int l = 0, r = -1;
// 初始化最小长度 len 为一个较大的值，并定义答案的左右边界
int len = Integer.MAX_VALUE, ansL = -1, ansR = -1;
int sLen = s.length();
// 移动右指针 r 来扩展窗口
while (r < sLen) {
++r;
// 如果当前字符在 t 中出现过，则将其加入当前窗口 cnt 字典
if (r < sLen && ori.containsKey(s.charAt(r))) {
cnt.put(s.charAt(r), cnt.getOrDefault(s.charAt(r), 0) + 1);
}
// 当窗口满足条件时（即包含了 t 中所有字符）
while (check() && l <= r) {
// 更新最小覆盖子串的长度和对应的起始位置
if (r - l + 1 < len) {
len = r - l + 1;
ansL = l;
ansR = l + len;
}
// 尝试缩小窗口，即移动左指针 l
if (ori.containsKey(s.charAt(l))) {
cnt.put(s.charAt(l), cnt.getOrDefault(s.charAt(l), 0) - 1);
}
++l;
}
}
// 如果找到了满足条件的最小子串，返回它；否则返回空字符串
return ansL == -1 ? "" : s.substring(ansL, ansR);
}
public boolean check() {
// 遍历 ori 字典的每一个键
for (Character key : ori.keySet()) {
// 获取 ori 中当前键对应的值，即 t 中该字符的数量
Integer val = ori.get(key);
// 如果 cnt 中该字符的数量小于所需数量，返回 false
if (cnt.getOrDefault(key, 0) < val) {
return false;
}
}
// 如果所有字符都满足条件，返回 true
return true;
}
}
getOrDefault(c, 0) 方法
getOrDefault 是 Java Map 接口中的一个方法，用来从映射（字典）中获取指定键的值。如果该键存在于映射中，则返回对应的值；如果该键不存在，则返回一个默认值。
方法签名
V getOrDefault(Object key, V defaultValue)
参数
key：要获取值的键。
defaultValue：当键不存在时返回的默认值。
返回值
如果 key 存在，则返回与 key 关联的值。
如果 key 不存在，则返回 defaultValue。
示例
假设有一个 Map：
Map<Character, Integer> map = new HashMap<>();
map.put('A', 1);
map.getOrDefault('A', 0)：返回1，因为键'A'在map中存在，且对应的值为1。map.getOrDefault('B', 0)：返回0，因为键'B'不存在，返回默认值0。
getOrDefault 与 get 的主要区别
-
默认值处理：
getOrDefault在键不存在时会返回一个用户指定的默认值。get在键不存在时会返回null。
-
代码简洁性：
- 使用
getOrDefault可以避免显式的空值检查，从而使代码更简洁。例如，如果用get，你可能需要手动处理null值：
- 使用
Integer value = map.get('B');
if (value == null) {
value = 0; // 或者其他默认值
}
使用 getOrDefault 可以直接得到一个合理的默认值：
Integer value = map.getOrDefault('B', 0);
3. 防止空指针异常
- 使用
getOrDefault可以有效避免空指针异常，因为它确保在键不存在时返回的值不是null，而是用户指定的默认值。 - 使用
get时，如果不进行null检查，可能会因为直接操作null导致空指针异常。
总结
getOrDefault(c, 0)：在Map中获取键c的值，如果不存在该键，则返回默认值0。它的优势是可以简化代码，避免null检查，并且安全地处理不存在的键。get(c)：在Map中获取键c的值，如果不存在该键，则返回null。使用时需要注意处理null，以避免空指针异常。
Integer
Integer 本质上是一个对象，可以为其赋值 null，也可以用来存储从 -2^31 到 2^31 - 1 范围内的任何整数值。这使得 Integer 能够在各种场合使用，特别是在需要对象的地方。