滑动窗口算法

滑动窗口是双指针的技巧之一。滑动窗口技巧一般用于解决子字符串问题。

参考地址，我个人是在刷LEETCODE438题时，采用了此框架，具体代码可以看这道题目的解析文档。

滑动窗口框架

/* 滑动窗口算法框架 */
void slidingWindow(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;
    
    int left = 0, right = 0;
    int valid = 0; 
    while (right < s.size()) {
        // c 是将移入窗口的字符
        char c = s[right];
        // 右移窗口
        right++;
        // 进行窗口内数据的一系列更新
        ...

        /*** debug 输出的位置 ***/
        printf("window: [%d, %d)\n", left, right);
        /********************/
        
        // 判断左侧窗口是否要收缩
        while (window needs shrink) {
            // d 是将移出窗口的字符
            char d = s[left];
            // 左移窗口
            left++;
            // 进行窗口内数据的一系列更新
            ...
        }
    }
}

在此框架中，几个注意点：

Need哈希表用于记录目标子字符串中，对应的字母与出现的频次，这代表了你的滑动窗口应当满足的最低要求。

哈希表的应用使得对目标字符串不限于顺序，而且保留了频次。在诸多题目中，均不限于顺序。
Windows哈希表用于记录当前滑动窗口内目标字符串出现的字母与频次。

在形式上与Need哈希表的形式是一摸一样的，但这里是记录的当前滑动窗口内符合条件的字母与频次，这代表Windows既可以不满足，也可以过满足。
right指针作为迭代下标
窗口扩大与窗口缩小的内部逻辑是对应的

算法思路

这里直接摘抄

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

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

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

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

4、重复第 2 和第 3 步，直到 right 到达字符串 S 的尽头。

这个思路其实也不难，第 2 步相当于在寻找一个「可行解」，然后第 3 步在优化这个「可行解」，最终找到最优解，也就是最短的覆盖子串。左右指针轮流前进，窗口大小增增减减，窗口不断向右滑动，这就是「滑动窗口」这个名字的来历。

下面画图理解一下，needs 和 window 相当于计数器，分别记录 T 中字符出现次数和「窗口」中的相应字符的出现次数。

初始状态：

增加 right，直到窗口 [left, right] 包含了 T 中所有字符：

现在开始增加 left，缩小窗口 [left, right]。

直到窗口中的字符串不再符合要求，left 不再继续移动。

之后重复上述过程，先移动 right，再移动 left…… 直到 right 指针到达字符串 S 的末端，算法结束。

现在开始套模板，只需要思考以下四个问题：

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

如果一个字符进入窗口，应该增加 window 计数器；

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

当 valid 满足 need 时应该收缩窗口；

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

如果一个字符将移出窗口的时候，应该减少 window 计数器

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

应该在收缩窗口的时候更新最终结果。