题目
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字母的最小子串。
输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"
思路
滑动窗口算法的思路是这样：
1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化left = right = 0，把索引闭区间 [left, right]称为一个「窗口」。
2、我们先不断地增加right指针扩大窗口[left, right]，直到窗口中的字符串符合要求（包含了T中的所有字符）。
3、此时，我们停止增加right，转而不断增加 left 指针缩小窗口 [left, right]，直到窗口中的字符串不再符合要求（不包含T 中的所有字符了）。同时，每次增加left，我们都要更新一轮结果。
4、重复第 2和第3步，直到right到达字符串S 的尽头。
这个思路其实是，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动。
伪代码
上述过程可以简单地写出如下伪码框架：
string s, t;
// 在 s 中寻找 t 的「最小覆盖子串」
int left = 0, right = 0;
string res = s;
while(right < s.size()) {
window.add(s[right]);
right++;
// 如果符合要求，移动 left 缩小窗口
while (window 符合要求) {
// 如果这个窗口的子串更短，则更新 res
res = minLen(res, window);
window.remove(s[left]);
left++;
}
}
return res;
如何判断 window 即子串 s[left...right] 是否符合要求，是否包含 t 的所有字符呢？
可以用两个哈希表当作计数器解决。用一个哈希表
needs记录字符串t中包含的字符及出现次数，用另一个哈希表window记录当前「窗口」中包含的字符及出现的次数，如果window包含所有needs中的键，且这些键对应的值都大于等于needs中的值，那么就可以知道当前「窗口」符合要求了，可以开始移动left指针了。
// 记录最短子串的开始位置和长度
string minWindow(string s, string t) {
int start = 0, minLen = INT_MAX;
int left = 0, right = 0;
// 相当于两个计数器
unordered_map<char, int> window;
unordered_map<char, int> needs;
for (char c : t) needs[c]++;
//map[key]++ 相当于 Java 的 map.put(key, map.getOrDefault(key, 0) + 1)
// 记录 window 中已经有多少字符符合要求了
int match = 0;
while (right < s.size()) {
char c1 = s[right];
if (needs.count(c1)) {
window[c1]++;
// 字符 c1 的出现次数符合要求了
if (window[c1] == needs[c1])
match++;
}
right++;
// window 中的字符串已符合 needs 的要求了
while (match == needs.size()) {
// 更新结果 res
if (right - left < minLen) {
// 更新最小子串的位置和长度
start = left;
minLen = right - left;
}
char c2 = s[left];
window[c2]--; // 移出 window
if (needs.count(c2)) {
window[c2]--;
if (window[c2] < needs[c2])
// 字符 c2 出现次数不再符合要求
match--;
}
left++;
}
}
return minLen == INT_MAX ?
"" : s.substr(start, minLen);
}
时间复杂度是 O(M + N).M 和 N 分别是字符串 S 和 TT的长度
题目二
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
说明：
字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。
字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
输入:
s: "cbaebabacd" p: "abc"
输出:
[0, 6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的字母异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的字母异位词。
只要把上一道题的代码改中更新 res 部分的代码稍加修改就成了这道题的解
vector<int> findAnagrams(string s, string t) {
// 用数组记录答案
vector<int> res;
int left = 0, right = 0;
unordered_map<char, int> needs;
unordered_map<char, int> window;
for (char c : t) needs[c]++;
int match = 0;
while (right < s.size()) {
char c1 = s[right];
if (needs.count(c1)) {
window[c1]++;
if (window[c1] == needs[c1])
match++;
}
right++;
while (match == needs.size()) {
// 如果 window 的大小合适
// 就把起始索引 left 加入结果
if (right - left == t.size()) {
res.push_back(left);
}
char c2 = s[left];
if (needs.count(c2)) {
window[c2]--;
if (window[c2] < needs[c2])
match--;
}
left++;
}
}
return res;
}
题目三
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
类似之前的思路，使用 window作为计数器记录窗口中的字符出现次数，然后先向右移动right，当window 中出现重复字符时，开始移动 left 缩小窗口，如此往复
需要注意的是，因为我们要求的是最长子串，所以需要在每次移动 right增大窗口时更新 res，而不是像之前的题目在移动 left 缩小窗口时更新 res。
int lengthOfLongestSubstring(string s) {
int left = 0, right = 0;
unordered_map<char, int> window;
int res = 0; // 记录最长长度
while (right < s.size()) {
char c1 = s[right];
window[c1]++;
right++;
// 如果 window 中出现重复字符
// 开始移动 left 缩小窗口
while (window[c1] > 1) {
char c2 = s[left];
window[c2]--;
left++;
}
res = max(res, right - left);
}
return res;
}
网友评论