[算法] leetcode 题型之 滑动窗口

理论

滑动窗口是双指针的其中一种用法，在 leetcode 上面也是不时能看到它的身影。
滑动窗口的双指针分别代表的是窗口的左边界和右边界，而我们需要做的，就是在每次循环时，右边界向右移，同时，去判断窗口内的数据是否依旧满足题解，如果不满足，则需要将左边界也向右移。
因此，滑动指针的题目可以用类似以下的模板进行改动：

void slidingWindow(string s) {
    int left = 0, right = 0;

    while (right < s.size()) {
    	// c 是窗口中新移入的字符
        char c = s[right];
        // 右边界右移
        right++;
        // 进行数据操作（如有）
        doSomeWork();

        while (windowTooLarge()) {
        	// d 是窗口中将要移出的字符
        	char d = s[left];
        	// 左边界右移
        	left++;
        	// 进行数据操作（如有）
        	doAnotherWork();
        }
    }
}

下面通过 leetcode 实战题来进一步说明如何使用这个模板。

实战

题目

leetcode 76
给你一个字符串 S、一个字符串 T，请在字符串 S 里面找出：包含 T 所有字符的最小子串。

示例：

输入: S = "ADOBECODEBANC", T = "ABC"
输出: "BANC"

说明：

• 如果 S 中不存这样的子串，则返回空字符串 “”。
• 如果 S 中存在这样的子串，我们保证它是唯一的答案。

题解

首先，我们有两个指针（在这里，我们用蓝色箭头代表左指针，黑色箭头代表右指针），分别指向开头；然后我们右边的指针不断右移，扩大当前窗口，直到所有字符串 T 中的字母都在窗口中出现。

此时，需要将左指针右移，并记录满足题目条件时最小的窗口大小所对应的左指针和右指针。

左指针右移后，发现不再满足题意，因此要将右指针右移至合适的位置。

此时，窗口内的字符都包含字符串 T 中的字母了，需要移动左指针。

以此类推，不断通过右指针扩大窗口至符合条件，左指针不断缩小窗口，直至不再满足题目条件。直到遍历完整个字符串，得到窗口最小的时候对应的左右指针的下标。

代码

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;
        
        int left = 0, right = 0;
        int valid = 0;
        int start = 0, len = INT_MAX; 
        // len 赋值为极大值，如果所有字符都不满足，则输出空字符串
        while (right < s.size()) {
            // c 是将移入窗口的字符
            char c = s[right];
            // 右边界右移
            right++;
            // 进行窗口内数据的一系列更新
            // 统计当前窗口中出现所需字母的次数
            // 如果出现了所有字符，那么 valid == need.size()
            if (need.count(c)) {
                window[c]++;
                if (need[c] == window[c]) {
                    valid++;
                }
            }
            
            // 判断左侧窗口是否要收缩
            while (valid == need.size()) {
                if (right - left < len) {
                    start = left;
                    len = right - left;
                }
                // d 是将移出窗口的字符
                char d = s[left];
                // 左移窗口
                left++;
                if (need.count(d)) {
                    if (need[d] == window[d]) {
                        valid--;
                    }
                    window[d]--;
                }
            }
        }
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};