【算法】滑动窗口

1.概述

（1）滑动窗口可以用以解决数组/字符串的子元素相关问题，并且可以将嵌套的循环问题，转换为单循环问题，从而降低时间复杂度。故滑动窗口算法的复杂度一般为 O(n)。

（2）滑动窗口的基本思想如下：

• 首先使用双指针维护一个子数组，别称为 left 和 right。left 指向窗口的左端点，right 指向窗口的右端点。如下图所示：
  
• 窗口随着 right 指针向右滑动开始遍历整个数组区间（即增大窗口）；

• 而在每次迭代内部（即针对每一次 right）要对子数组区间是否满足要求进行判断。如果子数组区间不能够满足条件则将 left 指针向右移动（即缩小窗口），这样窗口就实现了向右滑动。
  

2.算法框架

滑动窗口的算法框架如下：

class Solution {
    /**
     * @param1: 待处理的序列，一般为数组或字符串等线性表
     * @description: 滑动窗口算法框架
     */
    public void slidingWindow(int[] nums) {
        //此处使用 HashMap 来表示滑动窗口，也可根据具体情况使用其它存储结构
        Map<Integer, Integer> window = new HashMap<>();
        int length = nums.length;
        //定义滑动窗口的左右端点，初始值均为 0
        int left = 0;
        int right = 0;
        while (right < length) {
            //即将移入窗口的元素
            int inEle = nums[right];
            //增大窗口
            right++;
            //更新窗口内的数据
            //...
            
            //判断窗口是否要缩小
            while (窗口需要缩小的条件) {
                //即将移出窗口的元素
                int outEle = nums[left];
                //缩小窗口
                left++;
                //更新窗口内的数据
                //...
            }
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32

3.应用

（1）下面以 LeetCode 中的76.最小覆盖子串这题为例，来使用上述的滑动窗口框架：

• 如果直接使用暴力穷举法，其思路为使用两层 for 循环来枚举 s 的所有子串，并且逐一判断每个子串是否包含字符串 t 中的所有字母，如果包含则更新答案。显然该方法的时间复杂度肯定超过 O(n²)，其代码结构大致如下所示：

for (int i = 0; i < s.length(); i++) {
    for (int j = i + 1; j < s.length(); j++) {
        // isIncluded(s, i, j) 用于判断子串 s[i...j] 是否包含字符串 t 中的所有字母
        if (isIncluded(s, i, j, t)) {
            //更新答案
        }
    }
}
1
2
3
4
5
6
7
8

• 使用滑动窗口算法的具体代码实现如下：

class Solution {
    public String minWindow(String s, String t) {
        int sLen = s.length();
        // window 中记录滑动窗口内的字符以及对应出现的次数
        HashMap<Character, Integer> window = new HashMap<Character, Integer>();
        // need 记录字符串 t 中的字符以及对应出现的次数
        HashMap<Character, Integer> need = new HashMap<Character, Integer>();
        //将字符串 t 中的字符存入哈希表 need 中，key/value 为字符/对应出现的次数
        for (int i = 0; i < t.length(); i++) {
            char c = t.charAt(i);
            need.put(c, need.getOrDefault(c, 0) + 1);
        }
        //定义滑动窗口的左右端点，初始值均为 0
        int left = 0;
        int right = 0;
        //valid 记录窗口中 t 中不重复字符的个数
        int valid = 0;
        //记录最小覆盖子串的起始索引以及长度
        int start = 0, minLen = Integer.MAX_VALUE;
        while (right < sLen) {
            char c = s.charAt(right);
            right++;
            //更新窗口内的数据，如果字符 c 存在于 t 中，则将其加入到 window 中
            if (need.containsKey(c)) {
                window.put(c, window.getOrDefault(c, 0) + 1);
                /*
                    如果t中所有的字符c都已经加入到窗口中
                    注意：使用"=="比较 Integer 类型的值时，值的范围只能在 -128 ~ 127 之间，否则会出错
                    详情请见https://www.cnblogs.com/mrhgw/p/10449391.html
                */
                if (window.get(c).equals(need.get(c))) {
                    valid++;
                }
            }
            //判断左侧窗口是否要收缩，t 中的所有字符都已经加入到窗口中
            while (valid == need.size()) {
                //更新最小覆盖子串
                if (right - left < minLen) {
                    start = left;
                    minLen = right - left;
                }
                //d 是即将移出窗口的字符
                char d = s.charAt(left);
                left++;
                //更新窗口内的数据
                if (need.containsKey(d)) {
                    if (window.get(d).equals(need.get(d))) {
                        valid--;
                    }
                    window.put(d, window.get(d) - 1);
                }
            }
        }
        return (minLen == Integer.MAX_VALUE) ? "" : s.substring(start, start + minLen);
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56

（2）大家可以去 LeetCode 上找相关的滑动窗口的题目来练习，或者也可以直接查看LeetCode算法刷题目录 (Java)这篇文章中的滑动窗口章节。如果大家发现文章中的错误之处，可在评论区中指出。