当前位置: 首页> 财经> 产业 > 【leetcode】滑动窗口专题

【leetcode】滑动窗口专题

时间:2025/7/11 14:32:22来源:https://blog.csdn.net/weixin_69380220/article/details/140278036 浏览次数:0次

文章目录

  • 1.长度最小的子数组
  • 2.无重复字符的最长子串
  • 3.最大连续1的个数III
  • 4.将x减小到0的最小操作数
  • 5.水果成篮
  • 6.找到字符串中所有字母异位词
  • 7.串联所有单词的子串
  • 8.最小覆盖子串

在这里插入图片描述

1.长度最小的子数组

在这里插入图片描述
leetcode 209.长度最小的子数组

看到这个题目,第一眼肯定想到的是暴力枚举,那我们就来枚举以下试试:
在这里插入图片描述

很明显,暴力枚举的方式会超时。

在这里插入图片描述

那有没有哪里能优化一下,让它不超时呢?我们来分析一下:

在暴力枚举中,我们的 right 每次都会回到left位置的下一个,然后和 left 一起重新枚举。

在这里插入图片描述
优化枚举具体步骤如下:

在这里插入图片描述

在上面的枚举过程中,我们的蓝色框就像是一个滑动的、大小不固定的窗口,我们称这种方式叫做滑动窗口

对与滑动窗口而言,无非就以下几个步骤:
在这里插入图片描述
每个题目窗口的起始、更新结果的位置是不固定的,具体情况具体分析。

按照滑动窗口的方法,我们的代码就不会超时啦。
在这里插入图片描述
简单分析以下时间复杂度:从代码看好像是O(n2),但是由于我们滑动窗口的思想,两个指针是同向遍历,而且不会回退;当right指针结束时,循环结束,所以它的时间复杂度是O(n)。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int ret = INT_MAX;int n = nums.size();int sum = 0;for(int left = 0, right = 0; right < n; right++)//right后移{//进窗口sum += nums[right];//判断窗口while(sum >= target){//符合条件,更新结果ret = min(ret,right - left + 1);sum -= nums[left];//出窗口left++;}  }if(ret == INT_MAX)return 0;elsereturn ret;}
};

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

在这里插入图片描述
leetcode 3.无重复字符的最长字串

这一题首先想到的方法无疑就是枚举,然后统计每个字符出现的次数;如果一个字符出现了两次,那么当前字符对应的字符串就是最长子串
在这里插入图片描述
我们发现,暴力枚举法也可以过
在这里插入图片描述

那有没有更优的解法呢?我们来分析一下
在这里插入图片描述
上述解法不就是滑动窗口吗?
在这里插入图片描述

此时的时间复杂度O(n)是不是比暴力枚举O(n2)更加优秀了

class Solution {
public:int lengthOfLongestSubstring(string s) {int n = s.size();int hash[128] = { 0 };int ret = 0;for(int left = 0, right = 0; right < n; right++){hash[s[right]]++;//入窗口,先记录当前while(hash[s[right]] > 1)//若s[right]重复{hash[s[left]]--;//出窗口left++;}ret = max(ret,right - left + 1);//更新结果}return ret;}
};

3.最大连续1的个数III

在这里插入图片描述
leetcode 1004.最大连续1的个数III

分析题目可知,其中0可以翻转的意思就是:0可以当作1来用。那我们的目标就是找一段包含1的个数最大连续的区间,该区间中0的个数不可以超过k。

这一题的暴力枚举法就不演示了,我们直接上滑动窗口。
在这里插入图片描述
在这里插入图片描述
这样我们的代码就过咯
在这里插入图片描述

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int n = nums.size();int zero = 0;//统计0的个数int ret = 0;for(int left = 0, right = 0; right < n; right++){//进窗口,判断是否是0if(nums[right] == 0)zero++;//判断0的个数是否大于kwhile(zero > k){//判断是否是0出窗口if(nums[left] == 0)zero--;left++;}//更新结果ret = max(ret,right-left+1);}return ret;}
};

4.将x减小到0的最小操作数

在这里插入图片描述
leetcode 1658.将x减小到0的最小操作数

通过读题我们可以发现,它一会是左边,一会是右边,是不是很难控制;那应该怎么做呢?
正难则反

  • 我们在数组中找一块连续的区间,数组中去除该连续区间的内容,剩下的内容刚好等于x时,那我们是不是就找到了一种情况
  • 该连续区间就是数组中元素的总和减去x
  • 当在数组中找到的一块连续区间最长时,我们就找到了最佳的解决方案。

在这里插入图片描述
还是像前面的题目一样,使用滑动窗口。

在这里插入图片描述

class Solution {
public:int minOperations(vector<int>& nums, int x) {int ret = 0;int total = 0;int n = nums.size();for(auto e : nums)total += e; //求数组的和int target = total - x; //target为要找的连续区间的总大小if(target < 0)//细节return -1;if(total == x)return n;int sum = 0;for(int left = 0, right = 0; right < n; right++){sum += nums[right];//进窗口while(sum > target){sum -= nums[left];left++;}if(sum == target)//找到目标区间,取长的一个ret = max(ret,right - left + 1);}if(ret == 0)return -1;elsereturn n - ret;}
};

5.水果成篮

在这里插入图片描述
leetcode 904.水果成篮

这个题目这么长,它表达的是什么意思呢?

只有两个篮子,篮子里的水果只能有两种,并且不能跨越树木,求你所经过的树的最多的个数。
那又是求一段连续区间的长度,我们可以使用滑动窗口

在这里插入图片描述
那我怎么知道当前摘的水果有几种呢?----使用哈希表统计
在这里插入图片描述
我们可以发现,使用哈希表的消耗还是挺大的,能不能再优化一下呢?

由题目要求可知,种类是小于105的,所以我们可以直接使用一个数组+一个变量(记录种类)
在这里插入图片描述

这样我们的效率就提升了很多。
在这里插入图片描述

class Solution {
public:int totalFruit(vector<int>& fruits) {int n = fruits.size();int ret = 0;int hash[100000] = { 0 };int kinds = 0;for(int left = 0, right = 0; right < n; right++){if(hash[fruits[right]] == 0)//判断是否是新种类水果kinds++;hash[fruits[right]]++;//进窗口while(kinds > 2)//判断总类是否大于2{hash[fruits[left]]--;//出窗口if(hash[fruits[left]] == 0)kinds--;  //去除该种类left++;}ret = max(ret,right - left + 1);}return ret;}
};

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

在这里插入图片描述

leetcode 438.找到字符串中所有字母异位词

分析题目可知,就是在s串中找出p串(p串中的字符顺序可打乱)。
那我们就可以找一个长度和p相等,且字符种类、个数和p串相等的子串即可

所以我们可以使用两个哈希表,分别统计p串和s串中字符的种类和个数。

那我们先使用暴力枚举的方式试一下:
在这里插入图片描述
在这里插入图片描述

那两个哈希表是如何进行比较的呢?

  1. 首先使用hash1记录p串中字符的类型个数
  2. 遍历s,找长度和p相等的子串,同时hash2存放当前字符
    a、若hash2[right] <= hash1[right]时,“有效字符”种类增加
    b、若hash2[right] > hash2[right],“有效字符”种类不变

在这里插入图片描述
暴力枚举的方式确实可以过,但效率比较低下。
既然是找一段连续的区间,那能不能使用滑动窗口呢?我们来试一下
在这里插入图片描述
这样我们的效率就高很多了
在这里插入图片描述

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;int len = p.size();int hash1[128] = { 0 };for(auto e: p)hash1[e]++;//统计p串的种类int n = s.size();int hash2[128] = { 0 };//统计子串种类int kinds = 0;int tmp = 0;for(int left = 0,right = 0; right < n ; right++){hash2[s[right]]++; //进窗口tmp++;//子串长度增加if(hash2[s[right]] <= hash1[s[right]])kinds++;//"有效字符"种类增加if(tmp > len){if(hash2[s[left]] <= hash1[s[left]])kinds--;//left位置为“有效字符”,种类减少hash2[s[left]]--;tmp--;left++;}if(tmp == len)if(kinds == len)ret.push_back(left);}return ret;}
};

7.串联所有单词的子串

在这里插入图片描述

leetcode 30.串联所有单词的子串

这一题和前一道题目类似,只不过这里是将字符换成了字符串而已。因此我们还是使用:滑动窗口+哈希表的方式解决。
在这里插入图片描述

解题步骤:

  1. 先使用hash1统计words中字符串的种类
  2. 使用滑动窗口(由于字符串的长度是固定的,所以可以直接跳跃长度)
    a、定义起始:left、right
    b、字符串进窗口,需要使用字符串的函数substr进行裁剪
    c、判断字符串的种类
      是否出窗口
      更新结果

在这里插入图片描述
然而,代码只过了一部分,分析一下它的测试用例发现,
在这里插入图片描述
这样代码就过啦!

在这里插入图片描述

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string,int> hash1;for(auto& e : words)hash1[e]++;//统计要求的字符串种类int n = s.size();int len = words[0].size();//固定的字符串长度int m = words.size();//数组长度for(int i=0; i < len; i++){unordered_map<string,int> hash2;int count = 0;for(int left = i, right = i; right <= n -len; right+= len){string in = s.substr(right,len);//裁剪字符串hash2[in]++;//进窗口if(hash2[in] <= hash1[in])count++;//统计当前字符串数量if(right - left + 1 > m*len)//判断字符串数量是否大于字符数组{string out = s.substr(left,len);if(hash2[out] <= hash1[out])count--;hash2[out]--;//出窗口left += len;}if(count == m)ret.push_back(left);}}return ret;}
};

8.最小覆盖子串

在这里插入图片描述
leetcode 76.最小覆盖子串

该题和上一题的解题思路差不多,也是在s串中找t串的全部字符,只不过这里要将找到的字符串的最小的一个返回而已。

我们依旧使用滑动窗口+哈希表的方式解决。

  1. 使用hash1统计t串中字符的种类和数量
  2. 滑动窗口:定义起始位置 left, right
    a、进窗口
    b、判断是否出窗口
    c、更新结果(仅需记录串的起始位置和长度,最后在切割子串)

在这里插入图片描述

在代码中在记录字符串的起始位置和长度即可,这样我们的代码就过啦。

在这里插入图片描述

class Solution {
public:string minWindow(string s, string t) {int hash1[128] = { 0 };for(auto e : t)hash1[e]++;//统计t串的字符种类和数量int m = t.size();int n = s.size();int hash2[128] = { 0 };int count = 0;int start = 0;int len = INT_MAX;for(int left = 0, right = 0; right < n; right++){hash2[s[right]]++;//进窗口if(hash2[s[right]] <= hash1[s[right]])//是否更新有效字符count++;while(count >= m)//是否出窗口{if(count == m)//找到符合种类的子串{//取长度小的一个int curlen = right - left + 1;if(curlen < len){start = left;len = curlen;}}//出窗口if(hash2[s[left]] <= hash1[s[left]])count--;hash2[s[left]]--;left++;}}if(len == INT_MAX)return "";elsereturn s.substr(start,len);}
};
关键字:【leetcode】滑动窗口专题

版权声明:

本网仅为发布的内容提供存储空间,不对发表、转载的内容提供任何形式的保证。凡本网注明“来源:XXX网络”的作品,均转载自其它媒体,著作权归作者所有,商业转载请联系作者获得授权,非商业转载请注明出处。

我们尊重并感谢每一位作者,均已注明文章来源和作者。如因作品内容、版权或其它问题,请及时与我们联系,联系邮箱:809451989@qq.com,投稿邮箱:809451989@qq.com

责任编辑: