滑动窗口
目录
什么问题适用滑动窗口
对于连续子序列问题，可以使用滑动窗口。例如按要求得到最长/短的序列
滑动窗口算法框架
int low = 0, high = 0;
while (high < nums.size()) {
// 增大窗口
window.addLast(nums[high]);
high++;
while (window needs shrink) {
// 缩小窗口
window.removeFirst(nums[low]);
low++;
}
}滑动窗口方法需要考虑两个问题
- 何时满足题目条件
可能需要用到哈希表来统计元素出现情况
-
何时缩小范围
当high移动到第一次（不）满足题目要求后，移动low来缩小范围
-
何时记录结果
如果要记录最长序列则在缩小范围前记录
如果要记录最短序列则在缩小范围后记录
最小覆盖子串
题目
给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串，则返回空字符串 "" 。
示例 1：
输入：s = “ADOBECODEBANC”, t = “ABC” 输出：“BANC” 解释：最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、‘B’ 和 ‘C’。
解析
现考虑以下几个问题：
- 何时满足题目条件：当前字符串包含t
- 何时缩小范围：满足题目要求后
- 何时记录结果：由于要求最小串，所以在缩小范围后记录
核心代码
//...
while (high < s.size()) {
umap[s[high]]++;
// 缩小范围
while (is_valid(umap, target_umap)) {
int len = high - low + 1;
if (len < min_len) {
min_len = len;
result_l = low;
result_h = high;
}
umap[s[low]]--;
if (!is_valid(umap, target_umap)) {
umap[s[low]]++;
break;
} else
low++;
}
high++;
}
//...
字符串排列
题目
给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的 排列。如果是，返回 true ；否则，返回 false 。
换句话说，s1 的排列之一是 s2 的 子串 。
输入：s1 = “ab” s2 = “eidbaooo” 输出：true 解释：s2 包含 s1 的排列之一 (“ba”).
解析
现考虑以下几个问题：
-
何时满足题目条件：当前字符串包含t
-
何时缩小范围：满足题目要求后
-
何时记录结果：在缩小范围后，由于子串必须连续，所以要看下满足条件的子串是否和目标串大小相同。
相同则直接返回，否则low从high开始继续移动滑动窗口
核心代码
//...
while (high < int(s2.size())) {
high++;
if (target_map.count(s2[high]) != 0) {
src_map[s2[high]]++;
if (src_map[s2[high]] == target_map[s2[high]])
current_valid_count++;
}
if (current_valid_count == target_valid_count) // 收缩 low
{
while (target_map.count(s2[low]) == 0 ||
(target_map.count(s2[low]) != 0 &&
src_map[s2[low]] - 1 >= target_map[s2[low]])) {
if (target_map.count(s2[low]) != 0)
src_map[s2[low]]--;
low++;
}
if (high - low + 1 == s1.size())
return true;
}
}
//...
无重复字符的最长子串
题目
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。
输入: s = “abcabcbb” 输出: 3 解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
解析
现考虑以下几个问题：
- 何时满足题目条件：当前字符串不包含重复字符
- 何时缩小范围：第一次不满足题目要求后
- 何时记录结果：由于记录的是最长子串，所以在缩小范围前记录
核心代码
pp
//...
while (high < int(s.size()) - 1) {
high++;
if (src_map.count(s[high]) == 0) {
src_map[s[high]] = 1;
max_size = max(max_size, high - low + 1);
} else {
// 收缩 low
while (s[low] != s[high]) {
if (src_map.count(s[low]) != 0)
src_map.erase(s[low]);
low++;
}
low++;
}
}
//...