问题描述
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
注意：
- 对于
t中重复字符，我们寻找的子字符串中该字符数量必须不少于t中该字符数量。 - 如果
s中存在这样的子串，我们保证它是唯一的答案。
解题思路
-
初始化: 创建两个计数器或哈希表，一个用于
t中的字符计数（t_count），一个用于当前窗口中的字符计数（window_count）。定义两个指针，left和right，表示窗口的左右边界。还需要定义have（当前窗口满足t需求的字符种类数）和need（t中总共需要的不同字符种类数）。 -
扩大窗口: 移动
right指针扩大窗口，直到窗口包含了t的所有字符。 -
收缩窗口: 一旦窗口满足条件（即包含了
t的所有字符），尝试通过移动left指针来缩小窗口，直到窗口不再满足条件。在此过程中，记录可能的最小窗口。 -
更新最小窗口: 在移动
left指针的同时，检查当前窗口的大小，如果当前窗口的大小比已知的最小窗口小，更新最小窗口。 -
重复: 重复步骤 2 和 3 直到
right指针到达s的末尾。 -
提取结果: 根据记录的最小窗口的位置和大小，返回最小覆盖子串。如果没有找到有效的子串，返回空字符串。
关键点
- 滑动窗口: 利用两个指针
left和right追踪当前考虑的s的子串。 - 动态调整: 根据
t的需求动态增加或减少窗口大小。 - 效率: 通过只让每个指针最多遍历
s一次来保持高效率。 - 字符计数: 使用哈希表对字符进行计数，以便快速检查窗口是否满足条件。
代码实现
class Solution {
public:string minWindow(string s, string t) {if (s.size() < t.size())return "";// 统计 t 中各字符的数量unordered_map<char, int> t_count;for (char c : t)t_count[c]++;// 滑动窗口内各字符的数量unordered_map<char, int> window_count;int have = 0; // 当前窗口中包含了 t 的哪些字符int need = t_count.size(); // t 中有多少不同字符需要被包含int left = 0; // 窗口左边界int right = 0; // 窗口右边界int min_length = INT_MAX;int min_left = 0; // 最小窗口的左边界索引while (right < s.size()) {char c = s[right];if (t_count.count(c)) {window_count[c]++;if (window_count[c] == t_count[c])have++;}// 当前窗口已经包含了 t 中的所有字符while (have == need) {// 更新最小窗口if (right - left + 1 < min_length) {min_length = right - left + 1;min_left = left;}// 开始缩小窗口char left_char = s[left];if (t_count.count(left_char)) {window_count[left_char]--;if (window_count[left_char] < t_count[left_char])have--;}left++;}right++;}return min_length == INT_MAX ? "" : s.substr(min_left, min_length);}
};