什么问题适用滑动窗口
对于连续子序列问题,可以使用滑动窗口。例如按要求得到最长/短的序列
滑动窗口算法框架
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++; } }
|
滑动窗口方法需要考虑两个问题
何时满足题目条件
可能需要用到哈希表来统计元素出现情况
何时缩小范围
当high移动到第一次(不)满足题目要求后,移动low来缩小范围
何时记录结果
如果要记录最长序列则在缩小范围前记录
如果要记录最短序列则在缩小范围后记录
最小覆盖子串
题目
给你一个字符串 s
、一个字符串 t
。返回 s
中涵盖 t
所有字符的最小子串。如果 s
中不存在涵盖 t
所有字符的子串,则返回空字符串 ""
。
示例 1:
输入:s = “ADOBECODEBANC”, t = “ABC”
输出:”BANC”
解释:最小覆盖子串 “BANC” 包含来自字符串 t 的 ‘A’、’B’ 和 ‘C’。
解析
现考虑以下几个问题:
- 何时满足题目条件:当前字符串包含t
- 何时缩小范围:满足题目要求后
- 何时记录结果:由于要求最小串,所以在缩小范围后记录
核心代码
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++; }
|
字符串排列
题目
给你两个字符串 s1
和 s2
,写一个函数来判断 s2
是否包含 s1
的 排列。如果是,返回 true
;否则,返回 false
。
换句话说,s1
的排列之一是 s2
的 子串 。
输入:s1 = “ab” s2 = “eidbaooo”
输出:true
解释:s2 包含 s1 的排列之一 (“ba”).
解析
现考虑以下几个问题:
何时满足题目条件:当前字符串包含t
何时缩小范围:满足题目要求后
何时记录结果:在缩小范围后,由于子串必须连续,所以要看下满足条件的子串是否和目标串大小相同。
相同则直接返回,否则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) { 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 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 { while (s[low] != s[high]) { if (src_map.count(s[low]) != 0) src_map.erase(s[low]); low++; } low++; } }
|