0%

滑动窗口

什么问题适用滑动窗口

对于连续子序列问题,可以使用滑动窗口。例如按要求得到最长/短的序列

滑动窗口算法框架

1
2
3
4
5
6
7
8
9
10
11
12
13
int low = 0, high = 0;

while (high < nums.size()) {
// 增大窗口
window.addLast(nums[high]);
high++;

while (window needs shrink) {
// 缩小窗口
window.removeFirst(nums[low]);
low++;
}
}

滑动窗口方法需要考虑两个问题

  1. 何时满足题目条件

    可能需要用到哈希表来统计元素出现情况

  2. 何时缩小范围

    当high移动到第一次(不)满足题目要求后,移动low来缩小范围

  3. 何时记录结果

    如果要记录最长序列则在缩小范围前记录

    如果要记录最短序列则在缩小范围后记录

最小覆盖子串

题目

给你一个字符串 s 、一个字符串 t 。返回 s 中涵盖 t 所有字符的最小子串。如果 s 中不存在涵盖 t 所有字符的子串,则返回空字符串 ""

示例 1:

输入:s = “ADOBECODEBANC”, t = “ABC”
输出:”BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’。

解析

现考虑以下几个问题:

  1. 何时满足题目条件:当前字符串包含t
  2. 何时缩小范围:满足题目要求后
  3. 何时记录结果:由于要求最小串,所以在缩小范围后记录

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//...        
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++;
}
//...

字符串排列

题目

给你两个字符串 s1s2 ,写一个函数来判断 s2 是否包含 s1 的 排列。如果是,返回 true ;否则,返回 false

换句话说,s1 的排列之一是 s2子串

输入:s1 = “ab” s2 = “eidbaooo”
输出:true
解释:s2 包含 s1 的排列之一 (“ba”).

解析

现考虑以下几个问题:

  1. 何时满足题目条件:当前字符串包含t

  2. 何时缩小范围:满足题目要求后

  3. 何时记录结果:在缩小范围后,由于子串必须连续,所以要看下满足条件的子串是否和目标串大小相同。

    相同则直接返回,否则low从high开始继续移动滑动窗口

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//...        
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。

解析

现考虑以下几个问题:

  1. 何时满足题目条件:当前字符串不包含重复字符
  2. 何时缩小范围:第一次不满足题目要求后
  3. 何时记录结果:由于记录的是最长子串,所以在缩小范围前记录

核心代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
//...       
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++;
}
}
//...