Algorithm进阶计划 -- 滑动窗口
2021-09-24 本文已影响0人
开心wonderful
滑动窗口算法
- 滑动窗口框架
- 滑动窗口运用
图片来源于网络
1. 滑动窗口框架
滑动窗口算法，核心思路是维护一个窗口，不断滑动，然后更新答案。大致逻辑如下：
int left = 0, right = 0;
while (right < s.size()) {
// 增大窗口
window.add(s[right]);
right++;
while (window needs shrink) {
// 缩小窗口
window.remove(s[left]);
left++;
}
}
上面时间复杂度是 O(N)，算法思路比较简单，但各种细节问题比较不好理清。
滑动窗口主要针对子串问题，这边整理了一套滑动窗口算法的代码框架如下：
/**
* 滑动窗口算法框架
*/
private void slidingWindow(String s, String t) {
HashMap<Character, Integer> need, window;
for (Character c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while (right < s.length()) {
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
todoSomethingRight();
// *** debug 输出的位置 ***
// Log...
// *** debug 输出的位置 ***
// 判断左侧窗口是否要收缩
while (windowNeedsShrink()) {
// d 是将移出窗口的字符
char d = s.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
todoSomethingLeft();
}
}
}
套用上面的框架，需要需改的三个地方是右移和左移窗口更新操作 todoSomethingRight()、todoSomethingLeft() 以及判断左侧窗口是否要收缩 windowNeedsShrink()。
2. 滑动窗口运用
2.1 最小覆盖子串
力扣 76 题如下：
最小覆盖子串
上述题目要在 S(source) 中找到包含 T(target) 中全部字母的一个子串，并且这个子串一定是所有可能子串中最短的。
运用滑动窗口的算法思路如下：
- 在字符串
S中使用双指针中的左右指针技巧，初始化left = right = 0，把索引左闭右开区间[left, right)称为一个窗口。
- 在字符串
- 先不断地增加
right指针扩大窗口[left, right)，直到窗口中的字符串符合要求（包含了T中的所有字符）。
- 先不断地增加
- 此时，停止增加
right，转而不断增加left指针缩小窗口[left, right)，直到窗口中的字符串不再符合要求（不包含T中的所有字符了）。同时，每次增加left都要更新一轮结果。
- 此时，停止增加
- 重复第 2 和第 3 步，直到
right到达字符串S的尽头。
- 重复第 2 和第 3 步，直到
上面第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解。
接下来用画图描述，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。
初始状态：
初始状态
增加 right，直到窗口 [left, right) 包含了 T 中所有字符：
第 2 步
开始增加 left，缩小窗口 [left, right):
第 3 步
直到窗口中的字符串不再符合要求，left 不再继续移动：
第 4 步
套用滑动窗口框架，代码实现如下：
/**
* 最小覆盖子串
*/
String minWindow(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
for (Character c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
// valid 变量：窗口中满足 need 条件的字符个数，
// 若 valid 和 need.size 的大小相同，则说明窗口已满足条件，已经完全覆盖了串T。
int valid = 0;
// 记录最小覆盖子串的起始索引及长度
int start = 0, len = Integer.MAX_VALUE;
while (right < s.length()) {
// 开始滑动
// c 是将移入窗口的字符
char c = s.charAt(right);
// 右移窗口
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
// 当发现某个字符在window的数量满足了need的需要，就要更新valid，表示有一个字符已经满足要求
valid++;
}
}
// 判断左侧窗口是否要收缩
while (valid == need.size()) {
// 当valid == need.size()时，说明T中所有字符已经被覆盖，已经得到一个可行的覆盖子串，
// 现在应该开始收缩窗口了，以便得到「最小覆盖子串」
// 在这里更新最小覆盖子串
if (right - left < len) {
start = left;
len = right - left;
}
// d 是将移出窗口的字符
char d = s.charAt(left);
// 左移窗口
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
// 移动left收缩窗口时，窗口内的字符都是可行解，
// 在收缩窗口的阶段进行最小覆盖子串的更新，以便从可行解中找到长度最短的最终结果
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
// 返回最小覆盖子串
return len == Integer.MAX_VALUE ? "" : s.substring(start, start + len);
}
值得注意是，上面两次对窗口内数据的更新操作是完全对称的。
2.2 字符串的排列
力扣 567 题如下：
字符串的排列
上面题目，相当给你一个 S 和一个 T，判断 S 中是否存在一个子串，包含 T 中所有字符且不包含其他字符。
套用滑动窗口框架，代码实现如下：
/**
* 字符串的排列
* <p>
* 判断 s 中是否存在 t 的排列
*/
boolean checkInclusion(String t, String s) {
HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
for (Character c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 判断左侧窗口是否要收缩
while (right - left >= t.length()) {
// 这里判断是否找到了合法的子串
if (valid == need.size()) {
return true;
}
char d = s.charAt(left);
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
// 未找到符合条件的子串
return false;
}
值得注意的是，由于排列长度一样，移动 left 缩小窗口的时机是窗口大小大于 t.size() 时，当发现 valid == need.size() 时，就说明窗口中就是一个合法的排列，立即返回 true。
2.3 找到字符串中所有字母异位词
力扣 438 题如下：
找到字符串中所有字母异位词
上面题目，相当于输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。
套用滑动窗口框架，代码实现如下：
/**
* 找到字符串中所有字母异位词
*/
public List<Integer> findAnagrams(String s, String t) {
HashMap<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
for (Character c : t.toCharArray()) {
need.put(c, need.getOrDefault(c, 0) + 1);
}
int left = 0, right = 0;
int valid = 0;
List<Integer> res = new ArrayList<>();// 记录结果
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
if (need.containsKey(c)) {
window.put(c, window.getOrDefault(c, 0) + 1);
if (window.get(c).equals(need.get(c))) {
valid++;
}
}
// 判断左侧窗口是否要收缩
while (right - left >= t.length()) {
// 当窗口符合条件时，把起始索引加入 res
if (valid == need.size()) {
res.add(left);
}
char d = s.charAt(left);
left++;
// 进行窗口内数据的一系列更新
if (need.containsKey(d)) {
if (window.get(d).equals(need.get(d))) {
valid--;
}
window.put(d, window.getOrDefault(d, 0) - 1);
}
}
}
return res;
}
上面和字符串的排列一样，找到一个合法异位词后将起始索引加入res 即可。
2.4 无重复字符的最长子串
力扣 3 题如下：
无重复字符的最长子串
这题不能直接套用滑动窗口的框架，但稍微改动下框架反而更简单了：
/**
* 无重复字符的最长字串
*/
public int lengthOfLongestSubstring(String s) {
HashMap<Character, Integer> window = new HashMap<>();
int left = 0, right = 0;
int res = 0; // 记录结果
while (right < s.length()) {
char c = s.charAt(right);
right++;
// 进行窗口内数据的一系列更新
window.put(c, window.getOrDefault(c, 0) + 1);
// 判断左侧窗口是否要收缩
while (window.get(c) > 1) {
char d = s.charAt(left);
left++;
// 进行窗口内数据的一系列更新
window.put(d, window.getOrDefault(d, 0) - 1);
}
// 在收缩窗口完成后更新res
res = Math.max(res, right - left);
}
return res;
}
上面当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口了。
值得注意的是，要在收缩窗口完成后更新 res，因为窗口收缩的 while 条件是存在重复元素，即收缩完成后一定保证窗口中没有重复。
小结：套用滑动窗口框架，可以有效针对子串、子数组的相关问题。
参考链接：
