算法核心框架-滑动窗口

一概述

核心框架如下：


/* 滑动窗口算法框架 */
void slidingWindow(string s) {
    // 用合适的数据结构记录窗口中的数据
    Hashmap<char, int> window;
    
    int left = 0, right = 0;
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        window.add(c)
        // 增大窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        // 注意在最终的解法代码中不要 print
        // 因为 IO 操作很耗时，可能导致超时
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            window.remove(d)
            // 缩小窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

其中两处 ... 表示的更新窗口数据的地方，到时候你直接往里面填就行了。

而且，这两个 ... 处的操作分别是扩大和缩小窗口的更新操作，等会你会发现它们操作是完全对称的。

滑动窗口算法的思路是这样：

1、我们在字符串 S 中使用双指针中的左右指针技巧，初始化 left = right = 0，把索引左闭右开区间 [left, right) 称为一个「窗口」。

💡

理论上你可以设计两端都开或者两端都闭的区间，但设计为左闭右开区间是最方便处理的。因为这样初始化 left = right = 0 时区间 [0, 0) 中没有元素，但只要让 right 向右移动（扩大）一位，区间 [0, 1) 就包含一个元素 0 了。如果你设置为两端都开的区间，那么让 right 向右移动一位后开区间 (0, 1) 仍然没有元素；如果你设置为两端都闭的区间，那么初始区间 [0, 0] 就包含了一个元素。这两种情况都会给边界处理带来不必要的麻烦。

2、我们先不断地增加 right 指针扩大窗口 [left, right)，直到窗口中的字符串符合要求（包含了 T 中的所有字符）。

3、此时，我们停止增加 right，转而不断增加 left 指针缩小窗口 [left, right)，直到窗口中的字符串不再符合要求（不包含 T 中的所有字符了）。同时，每次增加 left，我们都要更新一轮结果。

4、当left不断缩小，直到不再符合字符串要求时。重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

使用模板时候需要考虑以下四个问题：

当移动right扩大窗口时候，即加入字符时，应该更新哪些数据

什么条件下，窗口应该暂停扩大，开始移动left缩小窗口

当移动left缩小窗口，即移出字符时，应该更新哪些数据

我们要的结果应该在扩大窗口还是缩小窗口时候更新

二示例

以找字符串中最长无重复字母的长度为例：

给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度。


public int lengthOfLongestSubstring(String s) {
        // key是字符，value是字符对应的个数
        Map<Character, Integer> windowMap = new HashMap<>();

        int res = 0;
        int left = 0;
        int right = 0;
        while (right < s.length()) {
            char c = s.charAt(right);
            right++;
            // 更新窗口内数据
            windowMap.put(c, windowMap.getOrDefault(c, 0) + 1);

            // 判断是否要缩小左侧窗口
            while (windowMap.get(c) > 1) {
                char d = s.charAt(left);
                left++;
                // 更新窗口内数据
                windowMap.put(d, windowMap.get(d) - 1);
            }
            res = Math.max(res, right - left);
        }
        return res;
    }

算法核心框架-滑动窗口

一 概述

二 示例

一概述

二示例