当前位置：首页 > news >正文

[LC优选算法#2] 滑动窗口 | 长度最小的子数组 | 无重复字符的最长子串 | 最大连续1的个数

news 2026/6/10 10:01:11

1. 算法思想

滑动窗口的本质是：维护一个满足条件的连续子数组/子串，通过移动左右边界来“滑动”这个窗口，从而找到最优解。滑动窗口是更加严格的双指针算法，大致思路都是用两个不回退的指针维护窗口。而且滑动窗口仅支持元素为正数的情况，不适用于负数或0（出窗口的时机无法确定）。

基本步骤：进窗口 -> 判断条件 -> 出窗口 -> 更新结果
（更新结果的时机因题而异）

2. 经典例题

2.1 ⻓度最⼩的⼦数组

⻓度最⼩的⼦数组

解题思路：

暴力解法O(N^2)：从数组中的每个元素开始向后枚举，找出满足条件的最小长度。

显然，暴力解法中存在很多重复的计算。
例如下图，如果按照暴力枚举的方式统计，当2枚举结束后需要从3开始重新计算长度，但3之后的1，2都是没必要重新计数的。根据这一点，我们可以试着维护一个“窗口”来解决重复统计的耗时问题。

滑动窗口O(N)：这个窗口满足内部所有元素之和小于target的条件。如果窗口内元素之和大于等于target，则更新结果，然后在逐个排除左边元素的同时，继续判断是否符合条件并继续更新结果；如果元素之和不满足条件，则加入新元素。

时间复杂度：由于维护窗口的left和right指针都是不回退的，最坏情况是两者分别遍历一次数组，因此总共耗时<= 2*N，时间复杂度为O(N)。

classSolution{public:intminSubArrayLen(inttarget,vector<int>&nums){intn=nums.size();intlen=INT_MAX;intsum=0;for(intleft=0,right=0;right<n;right++){sum+=nums[right];while(sum>=target){len=min(len,right-left+1);sum-=nums[left];left++;}}returnlen==INT_MAX?0:len;}};

2.2 ⽆重复字符的最⻓⼦串

⽆重复字符的最⻓⼦串
解题思路：

暴力解法+哈希表O(N^2)：从数组中的每个元素开始向后枚举，找出满足条件的最大长度。用哈希表统计出字符出现的频次，来判断什么时候子串出现了重复元素。

显然，研究对象依旧是一段连续的区间，以下图为例，在枚举完d后，没有必要以e、a为起点重新向后枚举，因为重复元素a仍然在橙色区间中，枚举的长度只会更短。因此我们可以通过向右缩小窗口直至满足条件（绿色区间），然后继续让新元素进窗口。

2.滑动窗口+哈希表O(N)：右端元素进⼊窗⼝的时候，哈希表统计这个字符的频次：

如果这个字符出现的频次超过1，说明窗⼝内有重复元素，那么就从左侧开始划出窗⼝，直到这个元素的频次变为 1 ，然后再更新结果；
如果小于1，说明当前窗⼝没有重复元素，可以直接更新结果。

时间复杂度：由于维护窗口的left和right指针都是不回退的，最坏情况是两者分别遍历一次数组，因此总共耗时<= 2*N，时间复杂度为O(N)。

classSolution{public:intlengthOfLongestSubstring(string s){intleft=0;intright=0;intn=s.size();intmaxlen=0;vector<int>hash(128,0);//128个字符，用数组模拟哈希表while(right<n){hash[s[right]]++;while(hash[s[right]]==2)//加1在前判断在后则为2{hash[s[left++]]--;}maxlen=max(maxlen,right-left+1);right++;}returnmaxlen;}};

2.3 最⼤连续 1 的个数 III

最⼤连续 1 的个数 III

解题思路：

可以翻转最多 k 个 0 ，转化为找一个包含 k 个 0的最长区间。

暴力解法O(N^2)：以每个元素为起点，依次向后找最长的子数组。

题目包含连续区间，考虑用滑动窗口思想解决：

滑动窗口O(N)：窗口内部存放有k个0的连续子串，以子串中0的个数为判断条件，维护窗口，超出k个0则停止更新，left指针左移；不够k个0则right指针右移，更新窗口。

classSolution{public:intlongestOnes(vector<int>&nums,intk){intleft=0;intright=0;intzerocnt=0;intlen=0;intn=nums.size();while(right<n){if(nums[right]==0){zerocnt++;}while(zerocnt>k){if(nums[left++]==0){zero--;}}len=max(len,right-left+1);right++;}returnlen;}};