算法练习题10：leetcode76最小覆盖子串-滑动窗口

目录

---

题目

题目描述

约束条件

解决思路

代码

getOrDefault(c, 0) 方法

方法签名

参数

返回值

示例

getOrDefault 与 get 的主要区别

Integer 

---

题目

题目描述

给定两个字符串 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 由英文字母组成。

解决思路

这道题可以使用滑动窗口的技巧来解决：

1. 初始化：使用两个字典，一个存储目标字符串 t 中各字符的计数，一个存储当前窗口中各字符的计数。
2. 扩展窗口：使用右指针逐步扩展窗口，直到窗口包含了 t 中所有字符。
3. 缩小窗口：一旦窗口满足条件，使用左指针尝试缩小窗口以找到更小的符合条件的子串。
4. 更新最优解：在每次找到符合条件的窗口时，更新当前最小的覆盖子串的长度及其位置。
5. 返回结果：如果找到满足条件的子串，返回最小的那个；如果没有找到，返回空字符串。

代码

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;}// 尝试缩小窗口，即移动左指针 lif (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 中该字符的数量小于所需数量，返回 falseif (cnt.getOrDefault(key, 0) < val) {return false;}}// 如果所有字符都满足条件，返回 truereturn 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);

1. map.getOrDefault('A', 0)：返回 1，因为键 'A' 在 map 中存在，且对应的值为 1。
2. map.getOrDefault('B', 0)：返回 0，因为键 'B' 不存在，返回默认值 0。

getOrDefault 与 get 的主要区别

1. 默认值处理：

   • getOrDefault 在键不存在时会返回一个用户指定的默认值。
   • get 在键不存在时会返回 null。

2. 代码简洁性：

   • 使用 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 能够在各种场合使用，特别是在需要对象的地方。