分析
- 记录目标字符频率：
- 使用哈希表
hashT 记录字符串 t 中每个字符的频率。
- 维护当前窗口的字符频率：
- 使用另一个哈希表
hashS 记录当前窗口内字符的频率。
- 滑动窗口：
- 扩展窗口：从左到右遍历字符串
s，将当前字符加入窗口，并更新 hashS
- 满足条件：当窗口中的字符满足
t 中的所有字符（包括频率要求），记录当前窗口长度
- 收缩窗口：尝试从窗口左端收缩，以找到更小的满足条件的子串
- 更新结果：
- 如果窗口当前覆盖所有所需字符且长度更短，则更新结果字符串
时间复杂度
- 遍历字符串
s：每个字符至多被访问两次（一次扩展窗口，一次收缩窗口），时间复杂度为 O(n)
- 更新哈希表：更新和查询哈希表的操作时间复杂度为
O(1)
总时间复杂度：O(n)
空间复杂度
使用了两个哈希表存储字符频率，空间复杂度为 O(n)
C++代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
|
class Solution
{
public:
string minWindow(string s, string t)
{
std::unordered_map<char, int> hashS, hashT;
for (char c : t)
++ hashT[c]; // 记录目标字符串 t 的字符频率
int cnt = 0; // 当前窗口内满足条件的字符个数
std::string res; // 记录结果子串
for (int i = 0, j = 0; i < s.size(); ++i)
{
++ hashS[s[i]]; // 扩展窗口
if (hashS[s[i]] <= hashT[s[i]])
++ cnt; // 更新满足条件的字符数
// 收缩窗口：移除多余的字符
while (hashS[s[j]] > hashT[s[j]])
{
-- hashS[s[j]];
++ j;
}
// 检查当前窗口是否满足条件
if (cnt == t.size())
if (res.empty() || res.size() > i - j + 1)
res = s.substr(j, i - j + 1); // 更新结果
}
return res;
}
};
|
