「滑动窗口算法概述」

0 滑动窗口的思想

思想其实就是之前所说的双指针技巧，滑动窗口其实就是快慢指针的思想，两个指针所组成一个窗口，然后不断向某个方向进行平移。
基本框架和综合框架来自东哥，有兴趣可以关注他的公众号：

int left = 0, right = 0;
while (right < s.size())
{
	//增大窗口
	window.add(s[right]);
	++right;

	while (widow needs shrink)
	{	
		//缩小窗口
		window.remove(s[left]);
		++left;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

现在所要思考的就是什么时候扩大窗口，什么时候缩小窗口。

//滑动窗口算法框架
void SlidingWindow(string s)
{
	unordered_map<char, int> window;//Hashmap
	//判断key是否存在可以使用count(key)相当于java的containsKey(key)的方法
    while (right < s.size())
    {
        //c是将移入窗口的字符
        char c = s[right];
        //增大窗口
        ++right;
        //进行窗口内数据的一系列更新
        ...//根据具体题目

        //debug输出
        cout << "window: " << left << ", " << right << endl;
        //printf("window: [%d, %d]\n", left, right);
        
        //判断左侧窗口是否要收缩
        while (window needs shrink)
        {
            //d是将移出窗口的字符
            char d = s[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

滑动窗口算法的时间复杂度是$O(N)$，虽然有个嵌套的while，但是这两个指针都是在向右边滑动，没有减小，把left和right这之间的区域称之为窗口。这个数组/字符串中的每一个元素都只能进入窗口一次以及移出窗口一次，所以说滑动窗口算法计算其时间复杂度要计算均摊时间复杂度，并且搞清楚区间是左闭右开的！

1 刷题

1.1 最小覆盖子串

1.1.1 题解

子串问题大概率滑动窗口，在字符串s当中使用左右指针的技巧，首先按照框架初始化左右指针为0，然后进行窗口的滑动，首先不断增加right，这样我们的窗口就不断的扩大，直到我们的窗口中的字符串符合要求，也就是包含了T当中所有的字符，这就满足了题目的一个条件，之后，停止扩大窗口，即停止right的++，开始逐步减小窗口，++left，直到这个窗口中的字符串不再包含T当中的字符，同时，每次增加left减小窗口的时候都要进行窗口内容的更新，之后再重复上述步骤，直到窗口穿过字符串s。

思考，什么时候该扩大窗口，什么时候该暂停扩大并且开始缩小窗口，结果是在扩大窗口时更新还是缩小窗口时更新？

扩大窗口：valid还不满足的时候，就是这个窗口还不包含字符串t所要求的的所有字符的时候，我要扩大，先满足这个字符串t的所有要求。

缩小窗口：在满足字符串t所有字符的要求后，进行缩小，因为要找到尽可能短的字符子串。

更新结果：因为要找到尽可能小的子串，所以应该是在缩小窗口的时候去更新，因为缩小窗口的时候，我们窗口里的字符串都是符合条件的，都是包含字符串t的所有字符的。

1.1.2 Code

class Solution {
public:
    string minWindow(string s, string t) {
        //子串问题大概率滑动窗口
        unordered_map<char, int>need, window;
        //need就是我们需要凑足的字符有哪些
        //window就是记录窗口中有哪些字符
        //hashmap类型是char对应int，就是每个字符需要多少个
        //window就是去存储每个字符存在多少个
        for (char c : t) need[c]++;//把这个t当中每个字符做一个计数
        //走框架
        int left = 0, right = 0;//左闭右开，初始化
        int valid = 0;//存储窗口中满足need条件的字符的个数，valid记录有多少个字符满足了条件，假如ABC，AB满足了valid就是2，还需要+1才能与need.size()相等
        //如果valid和need.size()的大小相同，说明该窗口满足条件，满足条件后开始缩小窗口
        int start = 0, len = INT_MAX;
        //因为要找子串，记录一下子串的长度，所以记录一下目标子串的起始索引和长度
        //走框架
        while (right < s.size())
        {
            //c是移入窗口的字符
            char c = s[right];
            //扩大窗口
            ++right;
            //进行窗口内数据的一系列更新
            if (need.count(c))
            {
                window[c]++;
                if (window[c] == need[c])
                {
                    ++valid;
                }
            }
            //判断左侧窗口是否要收缩
            while (valid == need.size())
            {
                //在这里更新最小覆盖子串
                if (right - left < len)//注意right是开区间，相减就是这个窗口的长度，左闭右开
                {
                    start = left;
                    len = right - left;
                }
                //d是将要移出窗口的字符
                char d = s[left];
                //缩小窗口
                ++left;
                //进行窗口内数据的一系列更新
                if (need.count(d))
                {
                    if (window[d] == need[d])//刚好符合要求
                    {
                        --valid;//刚好符合要求，移出后肯定不符合要求了，就要valid--
                    }
                    --window[d];
                }
            }
        }
        //返回最小覆盖子串
        return len == INT_MAX ? "" : s.substr(start, len);
    }
};
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
57
58
59
60

1.1.3 结果

1.2 字符串排列

1.2.1 题解

换句话来说，就是问是否存在s1的排列是s2的子串。代码与上一题基本一致，区别是缩小窗口的时机与之前不一致，left++的时机是窗口大小大于t.size()时，应为排列，所以长度显然是一样的，(right - left >= t.size()，这是一种定长窗口，因为要找的那个串的大小是一定的，不会像上一题那样扩展的很大或者收缩的很小，此题每次移出窗口只会移出一个字符不会移出多个。所以这个while改成if也是ok的。

1.2.2 Code

class Solution {
public:
    bool checkInclusion(string t, string s) {
        unordered_map<char, int> need, window;
        for (char c : t) need[c]++;

        int left = 0, right = 0;
        int valid = 0;
        while (right < s.size())
        {
            char c = s[right];
            right++;
            //进行窗口内数据的一系列更新
            if (need.count(c))
            {
                window[c]++;
                if (window[c] == need[c])
                {
                    valid++;
                }
            }

            //判断左侧窗口是否要收缩
            while (right - left >= t.size())
            {
                //在这里判断是否找到了合法的子串
                if (valid == need.size())
                {
                    return true;
                }
                char d = s[left];
                left++;
                //进行窗口内数据的一系列更新
                if (need.count(d))
                {
                    if (window[d] == need[d])
                    {
                        --valid;
                    }
                    window[d]--;
                }
            }
        }
        return false;
    }
};
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

1.2.3 结果

1.3 找到字符串中所有字母异位词

1.3.1 题解

与上题一样，只不过多了返回索引，在valid == need.size()的时候，记录一下索引即可。

1.3.2 Code

class Solution {
public:
vector<int> findAnagrams(string s, string t) {
    unordered_map<char, int> need, window;
    for (char c : t) need[c]++;

    int left = 0, right = 0;
    int valid = 0;
    vector<int> res; // 记录结果
    while (right < s.size()) {
        char c = s[right];
        right++;
        // 进行窗口内数据的一系列更新
        if (need.count(c)) {
            window[c]++;
            if (window[c] == need[c]) 
                valid++;
        }
        // 判断左侧窗口是否要收缩
        while (right - left >= t.size()) {
            // 当窗口符合条件时，把起始索引加入 res
            if (valid == need.size())
                res.push_back(left);
            char d = s[left];
            left++;
            // 进行窗口内数据的一系列更新
            if (need.count(d)) {
                if (window[d] == need[d])
                    valid--;
                window[d]--;
            }
        }
    }
    return res;
}

};
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

1.3.3 结果

2 总结

搞清楚滑动窗口的三个问题即可。