【leetcode】滑动窗口经典题目总结(c++实现)_c++ 滑窗

提示：文章写完后，目录可以自动生成，如何生成可参考右边的帮助文档

---

前言

滑动窗口是双指针一项非常重要的应用，可以应用再数组、字符串、链表中，可以分为定长滑动窗口与变长滑动窗口。本文对leetcode中常见的滑动窗口题目进行总结，以备后续复习使用，如有错误，恳请指出。

一、定长的滑动窗口

滑动窗口内长度不变，更新双指针应同步，窗口左边移除一个元素，同时窗口右侧移入一个元素，窗口的移动要时刻注意一进一出的特性，要维护与窗口有关的变量的变量，比如定长窗口内对应一个hash值，窗口移动要更新hash结果。

i++;
j++;
1
2

固定窗口的问题主要考查对窗口内数据如何处理，模板如下：

i[添加链接描述](https://leetcode.cn/problems/permutation-in-string/)nt left = 0;
int right = L -1 ;
while(right < s,size()){
	//维护变量
	//判断变量是否符合要求
	//更新左右指针
	left++；
	right++;
}
1
2
3
4
5
6
7
8
9

567. 字符串的排列

解题思路

• 固定窗口长度是s1.size(),从下标i = 0开始要用滑动窗口
• 需要找到窗口内字符串是否为s1的排列，排列与顺序无关，在窗口移动过程中维护一个hash数组(变量)
• 定长窗口一进一出的特性要保证进来的字符放到hash数组中，出去的元素移出hash数组(更新变量)
• 判断这个hash数组与s1对应的hash数组是否相同，更新答案
• 题目中说明字符串中只包含小写字母，可以用0-25作为键值

程序实现

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        
        if(s1.size()>s2.size())
            return false;
        vector<int>cnt1(26,0);
        vector<int>cnt2(26,0);

        for(int i = 0; i < s1.size(); i++)
            cnt1[s1[i]-'a']++;
        //初始化cnt2
        for(int i = 0; i < s1.size()-1; i++)
            cnt2[s2[i]-'a']++;
        int i =0, j = s1.size()-1;
        while(j < s2.size()){
            //更新变量
            cnt2[s2[j]-'a']++;
            //panduan
            
            if(cnt1 == cnt2)
                return true;
            //更新变量
            cnt2[s2[i]-'a']--;
            i++;
            j++;
        }
        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

219. 存在重复元素 II

解题方法

维护一个长度为k+1的定长窗口，并建议与窗口对应的hash表，用来表示窗口内出现元素的数量，如果窗口内某个元素对应数量为2，表示在窗口内出现了重复元素，返回true；从头到尾移动定长窗口，如果hash表没有出现元素数量为2，表示不存在重复元素，返回false，这个题目与字符串的排列相似，只不过判断条件发生了改变.

这里是：if(mp[nums[j]] == 2)
上一个题目是： if(cnt1 == cnt2)
1
2

程序实现

class Solution {
public:
    bool containsNearbyDuplicate(vector<int>& nums, int k) {
        //定长滑动窗口k+1
        //
        const int L = k+1 > nums.size() ? nums.size():k+1;
        cout<<L<<endl;
        unordered_map<int,int>mp;
        for(int i =0; i < L-1; i++){
            mp[nums[i]]++;
           // cout<<nums[i]<<" "<<mp[nums[i]]<<endl;
            if(mp[nums[i]] == 2)
                return true;
        }
        int i =0, j = L-1;
        while(j < nums.size()){
            //一进
            mp[nums[j]]++;
            //cout<<nums[j]<<" "<<mp[nums[j]]<<endl;
            if(mp[nums[j]] ==2)
                return true;
            //一出
            mp[nums[i]]--;
            i++;
            j++;
        }
        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

239. 滑动窗口最大值

解题思路

• 维护队列元素单调递减
• 保证元素在滑动窗口内，单调队列存储下标
• 采用双端队列deque实现单调队列

//双端队列
定义：deque<int>que;
//队尾插入元素
que.push_back(i);
//队尾删除   队头删除
que.pop_back();   que.pop_front();
//查看队头队尾元素
que.front();  que.back();
1
2
3
4
5
6
7
8

程序实现

class Solution {
public:
    vector<int> maxSlidingWindow(vector<int>& nums, int k) {
        //滑动窗口加单调队列。维护单调队列单调递减，取出队列首部元素
        //定长滑动窗口
        deque<int>que;
        vector<int>res;
        que.push_back(0);
        for(int i =1; i < k-1; i++){
            if(nums[i] < nums[que.back()])
                que.push_back(i);
            while(!que.empty() && nums[i] >= nums[que.back()])
                que.pop_back();
            que.push_back(i);
        }
        cout<<que.front()<<endl;
        int i = 0;
        int j = k-1;
        while(j < nums.size()){
            //更新单调队列
            if(nums[j] < nums[que.back()])
                que.push_back(j);
            while(!que.empty() && nums[j] >= nums[que.back()])
                que.pop_back();
            que.push_back(j);
            res.push_back(nums[que.front()]);
            if(que.front() <= i) que.pop_front();
            i++;
            j++;
        }
        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

二、变长的滑动窗口

一般来说，变长的滑动窗口右指针用来遍历，左指针用来收缩窗口，用满足条件的窗口更新答案

//右指针用来遍历
for(int i = 0; i < size; i++){
//收缩窗口
while(条件1 && 条件2){
	i++;
}

//更新变量

}
1
2
3
4
5
6
7
8
9
10

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

解题思路

外层指针遍历字符串中所有字符
当遇到重复字符时，内层指针开始收缩
遇到重复字符的条件是，hash表中已经存在元素
对于未出现重复字符的窗口，用左右指针更新最大长度

cnt[s[i]] ==2
or
map.find(s[i]) != mp.end()
1
2
3

程序实现

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //采用双指针 外层指针循环遍历遍历，内层指针出现重复开始移动
        //如何判断窗口内字符重复：构建哈希表
        //用0-255代替索引
        vector<int>cnt(256,0);
        int res= 0;
        int i =0;
        for(int j =0; j < s.size(); j++){
            if(cnt[s[j]] < 2)
                cnt[s[j]]++;
            //cout<<s[j]<<" "<<cnt[s[j]];
            while(cnt[s[j]] == 2 && i <= j){
                cnt[s[i]]--;
                i++;
            }  
            //G更新结果
            //cout << i <<" "<<j<<endl;
            res = max(res, j-i+1 );
        }
        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

209. 长度最小的子数组

解题思路

    //变长滑动窗口
    //满足条件sum < target时，右指针向后遍历
    //不满足条件时，
    //更新结果变量，左指针开始收缩
    //直至遍历到数组结尾
1
2
3
4
5

程序实现

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {

        int res = 1e9;
        int sum = 0;
        int j = 0;
        for(int i = 0; i < nums.size(); i++){
            if(sum < target) sum += nums[i];
            while(sum >= target && j <= i){
                res = min(res,i-j+1);
                sum -= nums[j];
                j++;
            }
        }
        if(res == 1e9)
            return 0;
        else 
            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

424.替换后的最长重复字符

解题思路

    子串长度与最多字符个数的差值来表时窗口内不同字符的数量
    //双指针 当窗口内不同字符个数小于k时，向右遍历，并更新长度
    //不满足条件时，窗口开始收缩
    //直至子串遍历结束
1
2
3
4

程序实现

class Solution {
public:
    int characterReplacement(string s, int k) {
       
        int max_s = 0;
        //建立一个辅助数组，统计窗口内出现的次数，窗口收缩时要给更新该辅助数组
        vector<int>cnt(26,0);
        int  res = 0;
        int i =0;
        for(int j = 0; j < s.size(); j++){
            if(j-i-max_s <= k){
                cnt[s[j]-'A']++;
                max_s = max(max_s,cnt[s[j]-'A']);
            }
            while(j-i+1- max_s > k){
                cnt[s[i]-'A']--;
                //更新最大值
                for(int k = 0; k < 26; k++)
                    max_s = max(max_s,cnt[k]);
                i++;
            }
            res = max(res, j-i+1);            
        }
        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