vcjmhg 的个人博客

自律者自由

  menu
80 文章
13419 浏览
1 当前访客
ღゝ◡╹)ノ❤️

滑动窗口常用技巧总结

概述

在解决 字串 问题时,滑动窗口技巧可能经常会使用,其本身思想并不难理解,难在灵活。因而本文从一个 最小覆盖字串 问题入手总结一个通用的算法框架以解决常见的滑动窗口问题。

算法与框架

下边我们先看一个最小覆盖子串问题:

image-20201113143843849

题目本身不难理解,主要就是从 S(source)中找到包含 T(target)中全部字幕的一个子串,顺序无所谓,个数相同且子串中一定是所有可能子串中最短的。

最简单的思路是通过暴力法,通过两层搜索来解决,但时间复杂度很高,甚至大于 O(n^2)。

此类问题实际上我们可以通过 滑动窗口 的思路来解决。具体思路如下:

  1. 在字符串 S 中使用双指针中左右指针的技巧,初始化 left = right = 0,把索引区间 [left,right] 称之为一个[窗口]。
  2. 不断的增加 right 指针扩大窗口 [left,right ],直到窗口中的字符串符合要求(窗口包含 T 中所有字符)。
  3. 停止增加 right,转而增加 left 指针,进而缩小窗口直到窗口不再符合要求。同时每增加一个 left 都要更新一轮结果。
  4. 重复 2 和 3,直到 right 达到字符串 S 的尽头。

整个过程思路并不难,其中第 2 步相当于在找一个可行解,第 3 步在优化这个可行解,每轮都进行结果更新,最后找到最优解。

下边我们结合整下边的图来理解算法的整个过程。needs 和 windows 相当于计数器,分别记录 T 中字符串出现的次数和窗口中的对应字符出现的次数。

第 1 步:初始状态,left 和 righ 都为 0

image-20201113145441247

第 2 步:向右移动 right 寻找可行解

image-20201113145521166

第 3 步:向右移动 left,优化可行解

image-20201113145601919

第 4 步:重复 2 和 3 直到,right 到达右边界

image-20201113145635325

上述过程可以简单写出如下的代码框架:

 1public String slidingWindow(String s, String t) {
 2	//定义两个窗口
 3	Map<Character, Integer> need = new HashMap<>(), window = new HashMap<>();
 4	// 初始化need窗口
 5	for (char c : t.toCharArray()) {
 6	  need.put(c, need.getOrDefault(c, 0) + 1);
 7	}
 8
 9	int left = 0, right = 0;
10	// 已经和need匹配的字符串个数 
11	int valid = 0;
12	while (right < s.length()) {
13	  char c = s.charAt(right);
14	  // move to right
15	  right++;
16	  // 进行窗口内一系列数据的更新
17	  ...
18
19	// 判断左侧窗口是否要收缩
20	while (window needs shrink) {
21	    // d 是将移出窗口的字符
22	    char d = s.charAt(left);
23	    // 左移窗口
24	    left++;
25	    // 进行窗口内数据的一系列更新
26	    ...
27	}
28}

其中两处 ... 表示更新窗口数据的地方,根据不同的问题,进行填充即可。

针对最小覆盖子串问题,开始套模板,只需要考虑如下四个问题:

  1. 移动 right 扩大窗口,即加入字符时需要考虑哪些数据?
  2. 什么条件下,窗口应该暂停扩大,开始移动 left 缩小窗口?
  3. 当移动 left 缩小窗口,即移除字符时,应该更新哪些数据?
  4. 我们要的结果应该在扩大窗口时还是缩小窗口时进行更新?

如果一个字符进入窗口,应该增加 window 计数器;如果一个字符将移出窗口的时候,应该减少 window 计数器;当 valid 满足 need 时应该收缩窗口;应该在收缩窗口的时候更新最终结果。

针对该问题我们将代码进行填充后得到如何解法:

 1string minWindow(string s, string t) {
 2    unordered_map<char, int> need, window;
 3    for (char c : t) need[c]++;
 4
 5    int left = 0, right = 0;
 6    int valid = 0;
 7    // 记录最小覆盖子串的起始索引及长度
 8    int start = 0, len = INT_MAX;
 9    while (right < s.size()) {
10        // c 是将移入窗口的字符
11        char c = s[right];
12        // 右移窗口
13        right++;
14        // 进行窗口内数据的一系列更新
15        if (need.count(c)) {
16            window[c]++;
17            if (window[c] == need[c])
18                valid++;
19        }
20
21        // 判断左侧窗口是否要收缩
22        //必须使用equlals来判断,不能使用 ==
23        while (valid.equals(need.size())) {
24            // 在这里更新最小覆盖子串
25            if (right - left < len) {
26                start = left;
27                len = right - left;
28            }
29            // d 是将移出窗口的字符
30            char d = s[left];
31            // 左移窗口
32            left++;
33            // 进行窗口内数据的一系列更新
34            if (need.count(d)) {
35                if (window[d].euqals(need[d])
36                    valid--;
37                window[d]--;
38            }                  
39        }
40    }
41    // 返回最小覆盖子串
42    return len == INT_MAX ?
43        "" : s.substr(start, len);
44}

应用

接下来我们再看一下另一个中等难度的题目字符串的排列

image-20201115195023834

题意很好理解,就是判断 s2 是否包含 s1 的某种排列。我们比较容易想到用暴力法。但会发现时间复杂度过高无法通过。然后考虑到是子串问题,尝试使用滑动窗口方法。

结合模板,考虑两个问题:

  1. 右侧窗口滑动时,做哪些操作
  2. 左侧窗口滑动的条件,以及所做操作

针对第一个问题,我们考虑到当右侧窗口滑动获取一个字符时要判断当前字符是否在 need 中,如果存在进行 windows 计数

针对第二个问题,如果窗口的长度大于 字符串t 的长度,则需要进行窗口左移操作,进行窗口“瘦身”

该问题具体代码实现如下:

 1public boolean checkInclusion(String t, String s) {
 2    if (t.length() > s.length()) {
 3      return false;
 4    }
 5    Map<Character, Integer> need = new HashMap<>();
 6    Map<Character, Integer> window = new HashMap<>();
 7    // init need
 8    for (char c : t.toCharArray()) {
 9      need.put(c, need.getOrDefault(c, 0) + 1);
10    }
11    // define variable
12    int left = 0, right = 0;
13    int valid = 0;
14    while (right < s.length()) {
15      char c = s.charAt(right);
16      right++;
17      // update right window
18      if (need.containsKey(c)) {
19        window.put(c, window.getOrDefault(c, 0) + 1);
20        if (need.get(c).equals(window.get(c))) {
21          valid++;
22        }
23      }
24      // shrink left window
25      // 每一次窗口的尺寸比need的尺寸大的时候都会进行瘦身操作,一直移动到比need的尺寸小1结束
26      while (right - left >= t.length()) {
27        if (valid == need.size()) {
28          return true;
29        }
30        char d = s.charAt(left);
31        left++;
32        if (need.containsKey(d)) {
33          if (window.get(d).equals(need.get(d))) {
34            valid--;
35          }
36          window.put(d, window.get(d) - 1);
37        }
38      }
39    }
40    return false;
41  }

总结

简单来说滑动窗口问题其实只要记下这个框架,大部分类似问题都可迎刃而解。

参考

  1. https://labuladong.gitbook.io/algo/shu-ju-jie-gou-xi-lie/2.5-shou-ba-shou-shua-shu-zu-ti-mu/hua-dong-chuang-kou-ji-qiao-jin-jie

标题:滑动窗口常用技巧总结
作者:vcjmhg
地址:https://vcjmhg.top/slide-window