【滑动窗口（全注释）—Leetcode刷题方法汇总】_930leetcode滑动窗口方法

---

---

前言

我们在做滑动窗口oj时，对最大最小滑动窗口总是傻傻分不清，总是把握不住什么时候缩小滑动窗口，什么时候控制下标，什么时候来判断，卡子今天来总结下滑动窗口oj，大小滑动窗口的解题框架

时间复杂度：o(n)
空间复杂度：o(n)

---

一、解题框架总结

1.1 最小滑动窗口

// 最小滑动窗口
        
        // 为满足所求条件，先创建初始变量

        for (size_t i = 0, j = 0; j < /*判断区间长度*/; j++)
        {
            // 将j位置元素计入窗口

            while(/*满足所求条件*/)
            {
                // 判断并修改窗口长度

                // 缩小窗口
            }
        }
		
		//（判断是否找到合适窗口，未找到根据题意另外返回）
        // 返回最终窗口/窗口长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

1.2 最大滑动窗口

// 最大滑动窗口
        
        // 为满足所求条件，先创建初始变量

        for (size_t i = 0, j = 0; j < /*判断区间长度*/; j++)
        {
            // 将j位置元素计入窗口

            while(/*不满足所求条件*/)
            {
                // 不得不缩小窗口
            }

            // 判断并修改窗口长度（保证每次满足所求条件下都有记录）
        }

		//（判断是否找到合适窗口，未找到根据题意另外返回）
        // 返回最终窗口/窗口长度
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

---

一、最小滑动窗口

1.1 LeetCode 209. 长度最小的子数组

套用最小滑动窗口框架框架

int minSubArrayLen(int target, vector<int>& nums)
    {
        // 求最小滑动窗口

        int sum = 0;
        // 求最小滑动窗口，初始化长度为最大值
        int len = INT_MAX;
        
		// i为开始位置，j为结束位置
        for (size_t i = 0, j = 0; j < nums.size(); j++) 
        {
            // 将j位置存入滑动窗口所求条件
            sum += nums[j];

            // i同时缩小（当i位置的元素删掉后不影响结果），归并到下面while中！！！

            // 满足滑动窗口要求，满足要求下缩小滑动窗口
            while ((long long)sum >= target)
            {
                // 判断并记录当前滑动窗口长度
                len = j - i + 1 < len ? j - i + 1 : len;

                // 缩小滑动窗口
                sum -= nums[i];
                ++i;
            }
        }
        // 如果未改变len，则说明未找到最小滑动窗口
        if (INT_MAX == len)
        {
            return 0;
        }
        return 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

---

1.2 LeetCode 76. 最小覆盖子串

首先我们如果还是按照上面的框架来写

string minWindow(string s, string t) 
    {
        // 最小滑动窗口

        // 因为所求条件需要统计各个元素的次数，所以我们可以使用哈希表
        unordered_map<char, int> window;
        // 记录当前滑动所缺元素的数量（为了避免每次都在哈希表中找）
        int cnt = t.size();
        // 记录满足条件、当前滑动窗口下的返回字符串，初始化为空串（根据题意）
        string ret("");
        // 求最小滑动窗口，初始化长度为最大值
        int len = INT_MAX;

        // 将t统计进wind
        for (auto& ch : t)
        {
            window[ch]++;
        }

        // 注：处理过程中，wind中的有效元素（t中元素）只可能为0 / 1
        // i表示滑动窗口起始位置，j表示结束位置
        for (size_t i = 0, j = 0; j < s.size(); j++)
        {
            // 先：判断j位置是否为有效元素（多余的有效元素也需记录），修改cnt
            if (window[s[j]] >= 0) // ????????????
            {
                // 因为只有wind中所缺元素才可能>=0
                --cnt;
            }
            // 再：将j位置元素引入所求条件中
            window[s[j]]--;
            
            for (auto& e : window)
            {
                cout << e.first << ":" << e.second << "  ";
            }
            cout << endl;
            cout << i << ":" << j << " cnt:" << cnt << endl;
            // i同时缩小（当i位置的元素删掉后不影响结果），归并到while中！！！

            // 当滑动窗口元素以满足所求条件，缩小滑动窗口
            while (0 == cnt)
            {
                // 判断并记录当前滑动窗口长度、并修改返回字符串
                if (j - i + 1 < len)
                {
                    len = j - i + 1;
                    ret = s.substr(i, j);
                }

                // 缩小滑动窗口
                
                // 判断如果i位置为有效元素，修改cnt；无效元素则直接缩小窗口
                if (window[s[i]] >= 0)
                {
                    window[s[i]]++;
                    // 只有我们初始将t统计进哈希表，t对应的元素此时才可能>=0
                    ++cnt;
                }
                ++i;
            }
        }
        // 如果未找到合适子串，则返回初始的空串
        return ret;
    }
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
61
62
63
64
65

无法用相同框架来判断某位置为有效元素

所以我们为了方便判断某位置是否为有效元素，引用两个哈希表

string minWindow(string s, string t) 
    {
        // 最小滑动窗口
        // 注：有效元素指：s中某元素（删掉后，s中对应元素个数小于t中对应元素的个数）

        // 因为所求条件需要统计各个元素的次数，所以我们可以使用哈希表
        unordered_map<char, int> hs;
        unordered_map<char, int> ht;
        // 记录s在[i,j]区间中满足t的元素的个数（为了避免每次都在哈希表中找）
        int cnt = 0;
        // 记录满足条件、当前滑动窗口下的返回字符串，初始化为空串（根据题意）
        string ret("");
        // 求最小滑动窗口，初始化长度为最大值
        int len = INT_MAX;

        // 将t统计进wind
        for (auto& ch : t)
        {
            ht[ch]++;
        }

        // i表示滑动窗口起始位置，j表示结束位置
        for (size_t i = 0, j = 0; j < s.size(); j++)
        {
            // 先将j位置元素引入所求条件中
            hs[s[j]]++;
            // 再判断j位置是否为有效元素（多余的有效元素也需记录），修改cnt
            // 因为我们先将s[j]加入hs数组中，再统计的，故等于也说明新加入的字符s[j]是必需的
            if (hs[s[j]] <= ht[s[j]])
            {
                // 说明该结束位置为有效字符，但还未达到ht中的数量
                ++cnt;
            }

            // i同时缩小（当i位置的元素无效），归并到while中！！！

            // 当滑动窗口元素已满足所求条件，缩小滑动窗口
            while (t.size() == cnt)
            {
                // 判断并记录当前滑动窗口长度、并修改返回字符串
                if (j - i + 1 < len)
                {
                    len = j - i + 1;
                    ret = s.substr(i, j - i + 1);
                }

                // 缩小滑动窗口
                
                // 判断如果i位置为有效元素，修改cnt，缩小窗口
                if (hs[s[i]] <= ht[s[i]])
                {
                    --cnt;
                }
                // 无效元素则直接缩小窗口
                hs[s[i++]]--;
            }
        }
        // 如果未找到合适子串，则返回初始的空串
        return ret;
    }
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 LeetCode 904. 水果成篮

套用最大滑动窗口框架

int totalFruit(vector<int>& fruits) 
    {
        // 最大滑动窗口
        // 题意：找连续且只存两种元素的最大滑动窗口

        // 为了记录窗口内各元素出现个数
        unordered_map<int, int> wind;
        int ret = 0;

        // i表示窗口起始位置，j表示窗口结束位置
        for (size_t i = 0, j = 0; j < fruits.size(); j++)
        {
            // 计入j位置元素
            wind[fruits[j]]++;
            
            // 同时增加i来不得不缩小窗口，在下while循环中统一进行

            // 窗口不满足所求条件，不得不缩小窗口
            while (wind.size() > 2)
            {
                // 不得不缩小窗口
                // 先将key为i位置删掉一个val
                wind[fruits[i]]--;
                if (0 == wind[fruits[i]])
                {
                    // 如果key为i，减去后val变为0.则将该pair删掉！！！~
                    wind.erase(fruits[i]);
                }
                ++i;
            }
            // 记录当前滑动窗口长度，在while外记录，保证窗口在满足条件时每次都会记录！！！~
            ret = j - i + 1 > ret ? j - i + 1 : ret;
        }
        return ret;
    } 
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

---

总结

这里对文章进行总结：
以上就是今天总结的内容，本文包括了我自己对滑动窗口问题解题的小经验，分享给大家。
真