力扣最热一百题——最小覆盖子串
目录
题目链接：76. 最小覆盖子串 - 力扣（LeetCode）
题目描述
示例
提示：
解法一：滑动窗口
1. 初始化
2. 构建 mapT
3. 滑动窗口
4. checkT 方法
5. 返回结果
Java写法：
运行时间
C++写法：
相比于Java主要改动：
运行时间
时间复杂度和空间复杂度
解法一极限优化
优化说明
运行时间
总结
题目链接：76. 最小覆盖子串 - 力扣（LeetCode）
注：下述题目描述和示例均来自力扣
题目描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
示例
示例 1：
输入：s = "ADOBECODEBANC", t = "ABC" 输出："BANC" 解释：最小覆盖子串 "BANC" 包含来自字符串 t 的 'A'、'B' 和 'C'。
示例 2：
输入：s = "a", t = "a" 输出："a" 解释：整个字符串 s 是最小覆盖子串。
示例 3:
输入: s = "a", t = "aa" 输出: "" 解释: t 中两个字符 'a' 均应包含在 s 的子串中， 因此没有符合条件的子字符串，返回空字符串。
提示：
m == s.lengthn == t.length1 <= m, n <= 10^5s和t由英文字母组成
解法一：滑动窗口
1. 初始化
- 使用两个
HashMap（mapS和mapT）来记录字符出现的次数。mapT用于存储字符串t中每个字符的出现次数，而mapS用于在滑动窗口过程中动态地记录当前窗口内字符的出现次数。 - 初始化结果子串的起始位置
resStart为 -1（表示还未找到符合条件的子串），和结果子串的长度resLen为s的长度加1（确保初始时，任何可能的子串长度都会比这个值小，从而能够更新）。
2. 构建 mapT
- 遍历字符串
t，统计每个字符的出现次数，并存储在mapT中。
3. 滑动窗口
- 使用两个指针
left和right来表示当前滑动窗口的左右边界。 - 使用一个
while循环来移动这两个指针，直到right指针超出字符串s的范围或当前窗口已经包含了t的所有字符（通过checkT方法检查）。 - 在循环内部，首先检查是否需要向右扩展窗口（即移动
right指针）。如果当前窗口不包含t的所有字符（!checkT(mapS, mapT)为真），则扩展窗口（即将s.charAt(right)加入到mapS中，并右移right指针）。 - 如果当前窗口已经包含了
t的所有字符，则尝试通过左移left指针来缩小窗口，直到窗口不再包含t的所有字符为止。在每次缩小窗口的过程中，都检查并更新结果子串的起始位置和长度（如果当前窗口长度更小的话）。
4. checkT 方法
- 这个方法用于检查
mapS是否包含了mapT中的所有字符，并且每个字符的出现次数都不少于mapT中对应字符的出现次数。 - 遍历
mapT中的每个字符，检查其在mapS中的出现次数是否满足条件。如果有任何一个字符不满足条件，则返回false；否则返回true。
5. 返回结果
- 循环结束后，如果找到了符合条件的子串（即
resStart不为 -1），则返回该子串；否则返回空字符串""，表示没有找到符合条件的子串。
Java写法：
class Solution {
public String minWindow(String s, String t) {
int lenS = s.length();
Map<Character,Integer> mapS = new HashMap<>();
Map<Character,Integer> mapT = new HashMap<>();
int resStart = -1;
int resLen = lenS + 1;
// 将t中的元素使用map集合存储起来
for (int i = 0; i < t.length(); i++) {
mapT.put(t.charAt(i),mapT.getOrDefault(t.charAt(i),0) + 1);
}
int left = 0;
int right = 0;
while (right < lenS || checkT(mapS, mapT)){
if (right > lenS || !checkT(mapS, mapT)){
// 如果当前窗口没有包含的话就添加元素,并右移right
mapS.put(s.charAt(right), mapS.getOrDefault(s.charAt(right),0) + 1);
right++;
}else {
// 如果当前窗口包含了的话,判断并更新结果的起始位置和长度
if (resLen > (right - left)){
resStart = left;
resLen = right - left;
}
// 就删除元素，并右移left
mapS.put(s.charAt(left), mapS.get(s.charAt(left)) - 1);
left++;
}
}
if(resStart != -1){
return s.substring(resStart, resStart + resLen);
}
return "";
}
/**
* 检查mapS是否包含了mapT中的全部字符
* @return
*/
private boolean checkT(Map<Character, Integer> mapS, Map<Character, Integer> mapT) {
for (Character character : mapT.keySet()) {
if (mapT.get(character) > mapS.getOrDefault(character, 0)){
return false;
}
}
return true;
}
}运行时间
520送给大家
C++写法：
class Solution {
public:
std::string minWindow(std::string s, std::string t) {
int lenS = s.length();
int lenT = t.length();
std::unordered_map<char, int> mapS;
std::unordered_map<char, int> mapT;
// 将t中的元素使用map集合存储起来
for (char c : t) {
mapT[c]++;
}
int resStart = -1;
int resLen = lenS + 1;
int left = 0, right = 0;
int required = mapT.size(); // 需要的不同字符数量
int formed = 0; // 当前窗口中满足条件的不同字符数量
while (right < lenS) {
// 添加右指针的字符
char c = s[right];
mapS[c]++;
// 如果当前字符在t中并且频率达标，则形成一个满足条件的字符
if (mapT.count(c) && mapS[c] == mapT[c]) {
formed++;
}
// 当当前窗口中包含了所有t的字符时，尝试收缩左指针
while (left <= right && formed == required) {
c = s[left];
// 更新最小子串的长度和位置
if (resLen > (right - left + 1)) {
resStart = left;
resLen = right - left + 1;
}
// 移除左指针指向的字符，并更新窗口
mapS[c]--;
if (mapT.count(c) && mapS[c] < mapT[c]) {
formed--;
}
left++;
}
right++;
}
// 如果没有找到符合条件的子串，则返回空字符串，否则返回最小子串
return resStart != -1 ? s.substr(resStart, resLen) : "";
}
};
相比于Java主要改动：
- 数据结构：Java 的
HashMap改为 C++ 的unordered_map。 - 字符串处理：Java 的字符串操作改为 C++ 的
string方法，例如s.substr。 - 类型和语法：调整了类型和语法，使其符合 C++ 规范。
- 字符计数：在删除字符时，如果计数为 0，使用
erase方法删除该字符。 - 主循环条件：适当调整了
while循环的条件，以确保在右指针达到字符串末尾时不会越界。
运行时间
时间复杂度和空间复杂度
 |  |
解法一极限优化
我就只写Java了，脑子要炸掉了
优化说明
-
窗口逻辑简化：原代码在主循环中条件判断较复杂，优化后将扩展右指针和收缩左指针的逻辑分开，使代码结构更清晰。
-
减少
mapS的使用：在添加和移除字符时，直接更新mapS的计数，而不是每次都调用getOrDefault，提高了性能。 -
优化
formed计数：通过使用formed变量来跟踪当前满足条件的字符数量，避免每次调用检查checkT方法，减少了不必要的遍历。 -
使用数组来存储结果：使用
int[] result数组来存储最小长度和指针位置，使代码更简洁，易于理解。
class Solution {
public String minWindow(String s, String t) {
int lenS = s.length(), lenT = t.length();
// 如果s的长度小于t的长度，则直接返回空字符串
if (lenS < lenT) return "";
// 创建mapT，存储t中每个字符的频率
Map<Character, Integer> mapT = new HashMap<>();
for (char c : t.toCharArray()) {
mapT.put(c, mapT.getOrDefault(c, 0) + 1);
}
// 创建mapS，存储当前窗口s中每个字符的频率
Map<Character, Integer> mapS = new HashMap<>();
int left = 0, right = 0;
int required = mapT.size(); // 需要的不同字符数量
int formed = 0; // 当前窗口中满足条件的不同字符数量
int[] result = {-1, 0, 0}; // result[0]: 最小长度, result[1]: 左指针位置, result[2]: 右指针位置
// 扩展右指针，形成窗口
while (right < lenS) {
char c = s.charAt(right);
mapS.put(c, mapS.getOrDefault(c, 0) + 1);
// 如果当前字符在t中，并且频率达到要求，则形成一个满足条件的字符
if (mapT.containsKey(c) && mapS.get(c).intValue() == mapT.get(c).intValue()) {
formed++;
}
// 当当前窗口中包含了所有t的字符时，尝试收缩左指针
while (left <= right && formed == required) {
c = s.charAt(left);
// 更新最小子串的长度和位置
if (result[0] == -1 || right - left + 1 < result[0]) {
result[0] = right - left + 1;
result[1] = left;
result[2] = right;
}
// 移除左指针指向的字符，并更新窗口
mapS.put(c, mapS.get(c) - 1);
// 如果移除后该字符不再满足条件，则减少formed计数
if (mapT.containsKey(c) && mapS.get(c).intValue() < mapT.get(c).intValue()) {
formed--;
}
left++;
}
right++;
}
// 如果没有找到符合条件的子串，则返回空字符串，否则返回最小子串
return result[0] == -1 ? "" : s.substring(result[1], result[2] + 1);
}
}
运行时间
这优化效果，牛不牛！！！！！
总结
我真的脑子爆炸了，┭┮﹏┭┮晚安
