滑动窗口算法详解（LeetCode题目归纳+代码模板+代码实现+个人感悟）_matlab使用滑动窗口找子序列

1 滑动窗口LeetCode题目归纳

• 链接如下：https://leetcode.cn/tag/sliding-window/problemset/（这里的有的也不是滑动窗口，主要看我的例题就行了）

2 什么样的题可以用该算法？

• 我觉得做题最重要的是看到这题要懂得用什么对应方法去求解，比如看到求最大最小等贪心优化问题就想到动态规划
• 如果你看到一题符合以下条件，那么用滑动窗口算法可以减少时间复杂度：
  • 一般是数字数组/字符串
  • 求数组的子序列/字符串子串需要满足给定的条件
  • 求最长/最短子序列/子串（或者是求最值）
  • 最最最重要的提示点是：必须是连续的，否则不可以用滑动窗口

3 算法的核心思想

• 滑动窗口算法顾名思义就是有一个滑动的窗口，这个窗口是由两个指针来构成的
• 一个left指针、一个right指针构成了滑动窗口的两个边界
• 初始状态是left指针和right指针都指向0（注意这里区别于对撞指针）
• 在我看来双指针可以分为滑动窗口+对撞指针
• 我认为该算法的底层原理是通过指针的移动来消除某一些可能性，这样可以避免无效计算
• 该算法分为三种类型：
  • 求最长子序列/串
  • 求最短子序列/串
  • 滑动窗口长度固定

4 算法的好处

• 好处在于可以大幅度减少时间开销，比如从一个O($n^2$)的时间开销摇身一变成为O(n)的时间开销

5 代码模板详解

• 这里我们先给出代码模板，但从来都是具体问题具体分析，这里仅给出简单模板
• 代码模板混合LeetCode例题解析，有助于理解模板
• 那我们就开始吧

求满足条件的长度最小的子序列/子数组

• 我们先来看代码模板

• 代码模板

int func(vector<int> nums)
{
    int left=0,right=0,var=0,ans=0,len=nums.size();//初始化left指针、right指针，再维护一个var变量，用来在指针移动过程中根据题意做出变化，再维护一个ans，也就是求的最小长度或者其他返回值
    while (right<len)
    {
        //现在用nums[right]来更新var
        while (var满足条件)
        {
            //更新最优结果ans
            //用nums[left]来更新var
            //窗口缩小，即left指针右移
        }
        right++;
	}
    return ans;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

• 核心思想是：当你移动right指针发现该子序列满足条件时，就会想要右移指针来贪心看看有没没有更短的符合条件的子序列

• 注意，维护的var变量不一定是一个变量，你也可以用集合，只要var能用来衡量是否满足子序列条件即可

• 例题1

209. 长度最小的子数组

给定一个含有 n 个正整数的数组和一个正整数 target 。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度**。**如果不存在符合条件的子数组，返回 0 。

示例 1：

输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。
1
2
3

示例 2：

输入：target = 4, nums = [1,4,4]
输出：1
1
2

示例 3：

输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
1
2

代码如下：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left=0,right=0,len=nums.size(),sum=0,ans=len+1;
        while (right<len)
        {
            sum+=nums[right];//维护sum
            while (sum>=target)//右移left指针缩小滑动窗口大小
            {
                if (right-left+1<ans) ans=right-left+1;//更新最优结果
                sum-=nums[left];//维护sum
                left++;//左指针右移
            }
            right++;
        }
        if (ans==len+1) return 0;//有时候会有这样需要特殊判断的，假如本题完全没有符合条件的子序列，那么ans一定还是初始值，所以直接返回0
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

解释：

• 本题就是一个很明显符合滑动窗口的问题：求满足某条件的连续子序列的最小长度
• 我们要维护的变量就是这个滑动窗口内数字的和，也就是当前一段子序列的和
• 求最小值，也就是长度最小的子数组，所以ans就设置为len+1，数组最长也不会超过len

---

---

求满足条件的长度最大的子序列/子数组

• 代码模板

int func(vector<int>& nums)
{
    int left=0,right=0,var=0,len=nums.size(),ans=0;
    while (right<len)
    {
        //用nums[right]更改var变量
        while (var不满足条件)
        {
            //用nums[left]来更新var变量
            left++;
        }
        if (xxxxxx) ;//更新最优结果ans
        right++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 注意这里更新最优结果在while循环的外面，原因是因为while循环内其实都是不符合条件的子序列，所以无需更新最优结果

• 这里要注意的是while循环的条件变成了var不满足条件，因为此时的算法思想是：随着right指针右移，窗口越变越大，但如果窗口内的子序列不满足条件，就要右移left指针，直到条件重新符合

• 例题1

3. 无重复字符的最长子串

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

示例 1:

输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
1
2
3

示例 2:

输入: s = "bbbbb"
输出: 1
解释: 因为无重复字符的最长子串是 "b"，所以其长度为 1。
1
2
3

示例 3:

输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。
1
2
3
4

代码如下：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int left=0,right=0,len=s.size(),ans=0;
        unordered_set<int> zifu;//注意这个其实就是var变量，用这个set来判断是否满足条件
        while (right<len)
        {
            while (zifu.find(s[right])!=zifu.end())//发现此时有重复字符了
            {
                zifu.erase(s[left]);
                left++;
            }
            if (right-left+1>ans) ans=right-left+1;
            zifu.insert(s[right]);//注意用right来改变变量时，可以在while循环后，这样可以避免一插入就认为不符合条件的情况
            right++;
        }
        return ans;
    }


};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

• 例题2

904. 水果成篮

你正在探访一家农场，农场从左到右种植了一排果树。这些树用一个整数数组 fruits 表示，其中 fruits[i] 是第 i 棵树上的水果 种类 。

你想要尽可能多地收集水果。然而，农场的主人设定了一些严格的规矩，你必须按照要求采摘水果：

• 你只有 两个 篮子，并且每个篮子只能装 单一类型 的水果。每个篮子能够装的水果总量没有限制。
• 你可以选择任意一棵树开始采摘，你必须从 每棵 树（包括开始采摘的树）上 恰好摘一个水果 。采摘的水果应当符合篮子中的水果类型。每采摘一次，你将会向右移动到下一棵树，并继续采摘。
• 一旦你走到某棵树前，但水果不符合篮子的水果类型，那么就必须停止采摘。

给你一个整数数组 fruits ，返回你可以收集的水果的 最大 数目。

示例 1：

输入：fruits = [1,2,1]
输出：3
解释：可以采摘全部 3 棵树。
1
2
3

示例 2：

输入：fruits = [0,1,2,2]
输出：3
解释：可以采摘 [1,2,2] 这三棵树。
如果从第一棵树开始采摘，则只能采摘 [0,1] 这两棵树。
1
2
3
4

示例 3：

输入：fruits = [1,2,3,2,2]
输出：4
解释：可以采摘 [2,3,2,2] 这四棵树。
如果从第一棵树开始采摘，则只能采摘 [1,2] 这两棵树。
1
2
3
4

示例 4：

输入：fruits = [3,3,3,1,2,1,1,2,3,3,4]
输出：5
解释：可以采摘 [1,2,1,1,2] 这五棵树。
1
2
3

• 这题和上面那题很像，都是说不能重复，但注意这是有区别的，上面那题是一点也不能重复，每一种类只能有一个，而这一题是每一种类会有多个，所以上一题可以用set，而这一题就不可以了，否则会影响left指针的移动，造成最终的答案错误

代码：

class Solution {
public:
    int totalFruit(vector<int>& fruits) {
        unordered_map<int,int> count;
        int left=0,right=0,ans=0,len=fruits.size();
        while (right<len)
        {
            count[fruits[right]]++;
            while (count.size()>2)
            {
                if (count[fruits[left]]==1) count.erase(fruits[left]);
                else  count[fruits[left]]--;
                left++;
            }
            if (right-left+1>ans) ans=right-left+1;
            right++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

• 例题3

1004. 最大连续1的个数 III

给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0 ，则返回 数组中连续 1 的最大个数 。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：[1,1,1,0,0,1,1,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 6。
1
2
3
4

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：[0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1]
粗体数字从 0 翻转到 1，最长的子数组长度为 10。
1
2
3
4

• 这题有意思的在于你不需要创建一个变量来判断是否满足条件，其给出的k本身就可以作为这样一个变量

代码：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int left=0,right=0,len=nums.size(),ans=0,num=k;
        while (right<len)
        {
            while (nums[right]==0 && k==0)
            {
                if (nums[left]==0) k++;
                left++;
            }
            if (nums[right]==0 && k) k--;
            if (right-left+1>ans) ans=right-left+1;
            right++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

• 例题4

674. 最长连续递增序列

给定一个未经排序的整数数组，找到最长且 连续递增的子序列，并返回该序列的长度。

连续递增的子序列 可以由两个下标 l 和 r（l < r）确定，如果对于每个 l <= i < r，都有 nums[i] < nums[i + 1] ，那么子序列 [nums[l], nums[l + 1], ..., nums[r - 1], nums[r]] 就是连续递增子序列。

示例 1：

输入：nums = [1,3,5,4,7]
输出：3
解释：最长连续递增序列是 [1,3,5], 长度为3。
尽管 [1,3,5,7] 也是升序的子序列, 但它不是连续的，因为 5 和 7 在原数组里被 4 隔开。 
1
2
3
4

示例 2：

输入：nums = [2,2,2,2,2]
输出：1
解释：最长连续递增序列是 [2], 长度为1。
1
2
3

代码如下：

class Solution {
public:
    int findLengthOfLCIS(vector<int>& nums) {
        int left=0,right=1,len=nums.size(),ans=-1;
        if (len<2) return 1;
        while (right<len)
        {
            while (nums[right]-nums[right-1]<=0 && left!=right)
            {
                left++;
            }
            if (right-left+1>ans) ans=right-left+1;

            right++;
        }
        return ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

滑动窗口大小固定

代码模板

int func(vector<int>& nums)
{
    int left=0,right=0,var=0,len=nums.size(),ans=0;
    while (right<len)
    {
        //用nums[right]更改var变量
        if ((right-left+1)==target_length)	//窗口大小达到指定值
        {
            if (满足条件) xxxxxxx;
            //用nums[left]来更新var变量
            left++;
        }
        right++;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

• 算法思想是：当固定长度窗口形成，那么将left和right指针同时向右移，并在过程中验证每一个窗口是否满足要求

例题1

567. 字符串的排列

给你两个字符串 s1 和 s2 ，写一个函数来判断 s2 是否包含 s1 的排列。如果是，返回 true ；否则，返回 false 。

换句话说，s1 的排列之一是 s2 的 子串 。

示例 1：

输入：s1 = "ab" s2 = "eidbaooo"
输出：true
解释：s2 包含 s1 的排列之一 ("ba").
1
2
3

示例 2：

输入：s1= "ab" s2 = "eidboaoo"
输出：false
1
2

提示：

• 1 <= s1.length, s2.length <= 104
• s1 和 s2 仅包含小写字母

解题思路

• 本题就是非常典型的固定大小滑动窗口问题，在主串中滑动一个长度为子串长度的窗口
• 判断这个固定窗口是否是子串s1的某种排列（这个通过统计每个字母来实现）
• 在主串s2中滑动这个窗口遍历所有可能
• 最重要的是在这个过程中可以不用一遍遍统计窗口内的字母组成，而是通过左指针减右指针加的方式，极大程度减少了时间开销

代码如下

class Solution {
public:
    bool checkInclusion(string s1, string s2) //s1是子串，s2是主串
    {
        int left=0,right=0,len1=s1.size(),len2=s2.size();
        vector<int> map1(26,0),map2(26,0);//用来记录串的字母组成
        for (auto i:s1)//先将子串统计好，用于跟主串窗口做对比
        {
            map1[i-'a']++;
        }
        //开始滑动窗口的主体
        while (right<len2)
        {
            map2[s2[right]-'a']++;//窗口右移后，添加窗口中最后一位的字母
            if ((right-left+1)==s1.size())//如果窗口长度达到目标值，判断窗口
            {
                if (judge(map1,map2))//判断是否是子串的某一种排列
                {
                    return true;
                }
                map2[s2[left]-'a']--;//窗口右移，去除左边的字母
                left++;
            }
            right++;//窗口右移
        }
        return false;
    } 
    bool judge(const vector<int>& map1,const vector<int>& map2)//判断字母组成是否相同
    {
        for (int i=0;i<26;i++)
        {
            if (map1[i]!=map2[i]) return false;
        }
        return true;
    }
};
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

例题2

【编程题】幼儿园有 N 个孩子玩游戏，随机围成了一个圈，老师最终想让所有男生排列到一起，所有女生排列到一起。每次老师可以命令两个孩子交换位置，求最小的命令次数：

N<=100

输入样例 1

3
FMF
1
2

输出样例 1

0
1

输入样例 2

4
FMFM
1
2

输出样例 2

1
1

解题思路

• 这题的难点在于得想到用滑动窗口来做
• 通过这题我又强化了一下解题思路，就是当存在一个序列（数组/字符串）时，对这个序列求一些最值，比如这题求最小的命令次数，就可以考虑用双指针或者滑动窗口来解决问题。
• 说回这题，我一开始就想到的解题思路（第六感）是一定要数出F的个数，但是我不知道如何去利用
• 其实当你数出来F的个数以后，就可以维护一个长度固定为F的滑动窗口，也就是说，这个滑动窗口里其实应该都是F
• 我们可以遍历从0到n-1的位置，含义是：这个F序列的起始位置
• 你可以想像现在已经是男生连续女生连续的情况了，也就是说所有的F都在一起，那么这个纯F序列的起始位置就有可能是0~n-1
• 我们用这样一个固定长度的滑动窗口来遍历所有可能出现的情况，在每个窗口中都要考虑当前窗口F的个数，来判断如果想要实现这个滑动窗口内全是F的话，需要交换几次F和M才能实现
• 话不多说上代码

代码实现

int solution(int n, string s)
{
    // 请添加具体实现
    int cnt_f = 0, cnt_m = 0;
    for (int i = 0; i < s.size(); i++)
    {
        switch (s[i])
        {
        case 'F':
            cnt_f++;
            break;
        case 'M':
            cnt_m++;
            break;
        };
    }
    // cout << "cnt_f=" << cnt_f
    //      << endl;
    int left = 0, right = 0, cnt_F = 0, cnt_M = 0;
    int target_len = cnt_f, min = INT_MAX;
    // cout << "target_len=" << target_len
    //      << endl;
    while (left < n)
    {
        // cout << "left=" << left << " right=" << right << endl;

        if (s[right] == 'F')
            cnt_F++;
        // cout << "cnt_F=" << cnt_F << endl;
        
        if (((right + n - left + 1) % n) == target_len)
        {
            if (target_len - cnt_F < min)
                min = target_len - cnt_F;
            if (s[left] == 'F')
                cnt_F--;
            left++;
        }

        right++;
        if (right == n)
            right = 0;
        
    }
    return min;
}
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

• 同样可以使用我上面给出的模板，但是要注意一点：注意题目中说的是围成一个圈，所以right到达尾部时需要重新返回头部，循环条件我们用left来替代，也就是维护这个全是F的序列的起始位置

个人感悟（重要）

• 我们以问答形式呈现，这些都是我自己在学习过程中我自己问自己的问题
• 求最长最短时，更新最优结果的if语句为啥一个在while循环内，一个在while循环外？
  • 答：因为更新最优结果时都必须在满足子序列符合条件的情况下，当求长度最小的子序列时，while循环内是满足条件的，所以if语句在while循环内；当求长度最大的子序列时，while循环内是不满足条件的，所以if更新最优结果应该在while循环外。
• 为啥求最短子序列while循环条件是满足条件而求最长子序列while循环条件是不满足条件？
  • 答：（1）当求最短子序列时，随着right指针右移，子序列越来越长，满足条件的概率就越来越大，一旦发现满足条件了，我们就要贪心缩小子序列长度，直到不满足条件；
  • （2）当求最长子序列时，随着right指针的右移，不满足条件的概率就越来越大，一旦发现不满足条件，就需要右移left指针使得序列重新满足条件，所以while循环内写不满足条件
• 滑动窗口问题最难的地方在于什么？
  • 答：我认为在掌握代码模板和滑动窗口思想的基础上，最难的就是将题目中的条件判断（符合XXXX的条件）用代码表示出来，这就跟动态规划问题，最难的就是定义状态数组的含义、递推公式以及初始化等。