小工具知识网

当前位置: 首页 > 行业知识 > 算法之滑动窗口

行业知识

算法之滑动窗口

2026-11-18 09:25:17 来源:互联网转载

题目1:209. 长度最小的子数组 - 力扣(LeetCode) 

��解法⼀(暴力求解):

思路:

从前往后, 枚举数组中的任意⼀个元素, 把它当成起始位置, 然后从这个起始位置开始, 然

后寻找⼀段最短的区间, 使得这段区间的和「⼤于等于」⽬标值.

将所有元素作为起始位置所得的结果中, 找到最⼩值即可。

解法⼆(滑动窗⼝):

思路:

由于此问题分析的对象是⼀段连续的区间, 因此可以考虑滑动窗⼝的思想来解决这道题.

这道题我们不妨换一个角度思考, 我们先不去思考怎么去针对这个最短区间做文章, 而是讨论每个下标i作为窗口的左端的情况下能取得的最短窗口长度, 在窗口缩短的过程中不断地更新这个最短长度, 最后的长度就是最短长度.

那怎么去求得这个最短长度呢?

 1. 将右端元素划⼊窗⼝中(right++), 统计出此时窗⼝内元素的和: 

如果窗⼝内元素之和sum⼤于等于 target : 更新长度len, 并且将左端元素划出去(left++), 更新sum, 为什么可以直接把最左端元素划出窗口?

因为此时窗口内的sum已经是以left为起始的最短满足条件的子数组了, 算上right之后的数窗口只会更长, 所以left为起点的这一组就判断完了.

2. left划出窗口后, 如果当前窗口的sum比target小, 肯定right要继续++, 但是当前窗口的sum也可能大于等于target, 所以应该继续判断sum去决定right是不是要继续++, 那此时是应该继续划出窗口呢? 还是right回退到left重新算一遍窗口内的sum呢? 

right不需要再回退到left重新来算一遍sum了, 抛开right对应的值, 此时窗口内的和肯定比上一个窗口小, 所以当前窗口以left为起点的子窗口的sum肯定更小,  所以right在上次的位置待着即可.

此时区间内的和要么是小于target的, 继续right++; 要么是大于等于target的, 也就是当前最小的一种子数组, 继续重复之前的步骤即可

可以注意到过程中left和right都是同向移动的, 这样的同向双指针称为滑动窗口: 

为何滑动窗⼝可以解决问题, 并且时间复杂度更低?

▪ 这个窗⼝寻找的是: 以当前窗⼝最左侧元素(记为left1 )为基准, 符合条件的情况.也就是在这道题中, 从left1开始, 满⾜区间和sum >= target 时的最右侧(记为right1 )能到哪⾥.

▪ 我们既然已经找到从 left1 开始的最优的区间, 那么就可以⼤胆舍去left1,但是如果继续像⽅法⼀⼀样,重新开始统计第⼆个元素(left2)往后的和, 势必会有⼤量重复的计算(因为我们在求第⼀段区间的时候, 已经算出很多元素的和了, 这些和是可以在计算下次区间和的时候⽤上的).

▪ 此时, rigth1 的作⽤就体现出来了, 我们只需将 left1 这个值从 sum 中剔除, 从right1这个元素开始, 往后找满⾜left2元素的区间(此时right1也有可能是满⾜的, 因为left1可能很⼩, sum 剔除掉left1之后, 依旧满⾜⼤于等于target ), 这样我们就能省掉⼤量重复的计算。

▪ 这样我们不仅能解决问题, ⽽且效率也会⼤⼤提升。


时间复杂度:虽然代码是两层循环,但是left指针和 right指针都是不回退的, 两者最多都往后移动n次, 因此时间复杂度是? O(N)  

class Solution {public:    int minSubArrayLen(int target, vector& nums)    {        int left = 0, right = 0, n = nums.size();        int sum = 0, len = INT_MAX;        while(right = target)            {                //更新最小长度                int newlen = right - left + 1;                len = len  

题目2:3. 无重复字符的最长子串 - 力扣(LeetCode) 

解法⼀(暴⼒求解):

思路:

枚举「从每⼀个位置」开始往后, ⽆重复字符的⼦串可以到达什么位置, 找出其中⻓度最⼤的即可.在往后寻找⽆重复⼦串能到达的位置时, 可以利⽤「哈希表」统计出字符出现的频次, 来判断什么时候⼦串出现了重复元素.

解法⼆(滑动窗⼝):

思路:

研究的对象依旧是⼀段连续的区间, 因此继续使⽤「滑动窗⼝」思想来优化, 

让滑动窗⼝满⾜: 窗⼝内所有元素都是不重复的。
做法:右端元素 ch 进⼊窗⼝的时候, 哈希表统计这个字符的频次.

▪ 如果这个字符出现的频次超过 1 , 说明窗⼝内有重复元素, 那么就从左侧开始划出窗⼝, 直到ch这个元素的频次变为1, 然后再更新结果, 因为left要跳过当前right指的重复元素, 才有机会得到新的最长子串, 否则每次都会被right卡***, 长度始终无法突破最开始的长度.

▪ 如果没有超过1, 说明当前窗⼝没有重复元素, 可以直接更新结果.

class Solution {public:    int lengthOfLongestSubstring(string s)     {        map m;        int left = 0,right =0;        int len = 0;        while(right  1)                m[s[left++]]--;//左边一直滑动,直到跳过重复字符            len = max(len,right - left + 1);//更新长度            right++;//向右滑动窗口        }        return len;    }};

题目3:1004. 最大连续1的个数 III - 力扣(LeetCode)

解法(滑动窗⼝):

思路:

不要去想怎么翻转, 这道题的结果⽆⾮就是⼀段连续的 1 中间塞了k 个0 , 因此, 我们可以把问题转化成:求数组中⼀段最⻓的连续区间, 要求这段区间内 0 的个数不超过 k 个.

既然是连续区间, 可以考虑使⽤滑动窗⼝来解决问题.

写法1: 

class Solution {public:    int longestOnes(vector& nums, int k)    {        int left = 0, right = 0;        int zerocount = 0;        int len = 0;        while(right  

 写法2:

class Solution{public:    int longestOnes(vector& nums, int k)    {        int ret = 0;        for(int left = 0, right = 0, zero = 0; right  k) // 判断                if(nums[left++] == 0) zero--; // 出窗⼝            ret = max(ret, right - left + 1); // 更新结果        }        return ret;    }    };

题目4:1658. 将 x 减到 0 的最小操作数 - 力扣(LeetCode) 

解法(滑动窗⼝):

思路:

题⽬要求的是数组「左端+右端」两段连续的和为 x 的最短数组, 信息量稍微多⼀些,不易理清

思路, 正难则反, 我们可以转化成求数组内⼀段连续的和为sum(nums) - x的最⻓数组。此时, 就是滑动窗⼝问题. 

class Solution {public:    int minOperations(vector& nums, int x)    {        int left = 0, right = 0;        int n = nums.size();        int sumi = 0, len = -1;        int sum = 0;        for(auto& e: nums)            sum += e;        while(right  sum - x)                sumi -= nums[left++];            if(sumi == sum - x)                len = max(len, right-left+1);            right++;        }                if(len == -1)            return -1;        return nums.size() - len;    }};

题目5:904. 水果成篮 - 力扣(LeetCode) 

解法(滑动窗⼝):
思路:

研究的对象是⼀段连续的区间, 可以使⽤滑动窗⼝思想来解决问题, 让滑动窗⼝满⾜:窗⼝内⽔果的种类只有两种.

做法: 右端⽔果进⼊窗⼝的时候, ⽤哈希表统计这个⽔果的频次, 这个⽔果进来后, 判断哈希表的

大小:

▪ 如果大小超过2: 说明窗⼝内⽔果种类超过了两种, 先记录结果然后出窗口, 从左侧开始依次将⽔果划出窗口直到哈希表的大小小于等于2, 然后更新结果;

▪ 如果没有超过2, 说明当前窗⼝内⽔果的种类不超过两种, 继续统计.

 while循环:

class Solution {public:    int totalFruit(vector& fruits)     {        unordered_map m;        int left = 0, right = 0, n = fruits.size(), ret = 0;        while(right  2)            {                if(--m[fruits[left]] == 0)                    m.erase(fruits[left]);                left++;            }            ret = max(ret, right - left);        }        return ret;    }};

 参考别人的for循环实现:

class Solution {public:    int totalFruit(vector& fruits) {        int hash[100001] = {0};        int ret = 0;        for(int left=0,right=0,kinds=0; right 2)            {                hash[fruits[left]]--;                if(hash[fruits[left]] == 0)//如果kinds减为0种类--                    kinds--;                left++;            }            ret = max(ret,right-left+1);        }        return ret;    }};

题目6:438. 找到字符串中所有字母异位词 - 力扣(LeetCode)

判断异位词只需要创建两个字母的哈希表, 如果哈希表相同, 那么这两个串就是异位词, 对于这题来说, 可以考虑用哈希表是否相等来判断异位词, 大思路还是滑动窗口, 而且这是一个定长的滑动窗口, 同样还是分为入窗口, 判断, 出窗口, 更新结果这几个步骤:

class Solution {public:    bool isEqual(int* h1, int* h2)    {        for(int i = 0;i m)//判断            {                hash1[s[left++]-'a']--;//出窗口            }            if(isEqual(hash1,hash2))                ret.push_back(left);            right++;        }          return ret;    }};

 但是判断哈希表是否相等的代价有点大了, 这题还好, 如果需要判断的是字符串等自定义类型的哈希表, 那代价就很大了, 所以考虑进行优化更新结果的判断条件:

利用一个变量count来统计窗口中有效字符的个数, 我们全程只需要去移动滑动窗口的同时去维护这个count, 通过比较count是否和p的长度相等, 即可判断是否是字母异位词:

如何去判断一个字符是否有效呢?

如果 hash1[s[right]-'a']

上一篇:哪里可以买到云服务器配件?

下一篇:小米购买华为服务器怎么用?