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

算法中的移动窗帘——C++滑动窗口算法详解

news 来源：原创 2025/6/9 19:35:24

1. 滑动窗口简介

滑动窗口是一种在算法中常用的技巧，主要用来处理具有连续性的子数组或子序列问题。通过滑动窗口，可以在一维数组或字符串上维护一个固定或可变长度的窗口，逐步移动窗口，避免重复计算，从而提升效率。常用于求解子数组的最大/最小值、满足条件的子数组个数等问题。

滑动窗口的两种类型

1. 固定大小的滑动窗口：窗口大小固定不变，通常适合于问题中要求找定长子数组的最大值、最小值等情况。
2. 可变大小的滑动窗口：窗口大小根据条件动态调整，通常适用于子数组和达到一定值或满足特定条件的情况。

滑动窗口的实现步骤

以可变大小的滑动窗口为例，一般步骤如下：

1. 初始化窗口的左右边界（例如 `left` 和 `right` 指针），并根据问题需求定义窗口内需要维护的变量（如窗口内的和、计数等）。
2. 移动右边界 `right`，将新元素加入窗口，并更新窗口内的变量。
3. 检查当前窗口是否满足条件。如果满足，记录答案（如更新最大/最小值），然后移动左边界 `left` 以缩小窗口，继续寻找其他符合条件的窗口。
4. 重复步骤 2 和 3，直到右边界遍历完数组。

应用场景

滑动窗口常用于以下几类问题：
- 子数组和问题（如最大、最小和）
- 子字符串问题（如最长无重复子串）
- 符合条件的区间统计

这种方法在处理需要频繁访问连续子序列的问题时具有高效性。

2. 长度最小的子数组

一、题目介绍

二、思路解析

方法一：暴力枚举

枚举将数组中的每个元素都当做起点，向后遍历数组寻找最短区间，最后找到将所有元素当做期待所得结果的最小值。

优化方法：滑动窗口：

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

（1）left = 0, right = 0

（2）进窗口

- 当窗口中的值小于target是，进窗口

（3）判断什么时候出窗口并更新结果

- 当窗口中的值大于等于target时，窗口中的值减去left位置的值（更新结果），出窗口（left++）

三、代码实现

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

. - 力扣（LeetCode）

为何滑动窗口可以解决问题，并且时间复杂度更低？

- 这个窗口寻找的是：以当前窗口最左侧元素（记为 left1 ）为基准，符合条件的情况。也就是在这道题中，从 left1 开始，满足区间和 sum >= target 时的最右侧（记为right1 ）能到哪里。

- 我们既然已经找到从 left1 开始的最优的区间，那么就可以大胆舍去 left1 。但是如

果继续像方法一⼀样，重新开始统计第二个元素（ left2 ）往后的和，势必会有大量重复

的计算。

- 此时， rigth1 的作用就体现出来了，我们只需将 left1 这个值从 sum 中剔除。从right1 这个元素开始，往后找满足 left2 元素的区间（此时 right1 也有可能是满足的，因为 left1 可能很小。 sum 剔除掉 left1 之后，依旧满足大于等于target ）。这样我们就能省掉大量重复的计算。

这样我们不仅能解决问题，而且效率也会大大提升。

时间复杂度：虽然代码是两层循环，但是我们的 left 指针和 right 指针都是不回退的，两者

最多都往后移动 n 次。因此时间复杂度是 O(N)

总结一下：优化算法将每次找到符合条件的区间，right都需要重新从新left位置开始遍历数组这一过程省去了。

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

一、题目介绍

二、思路解析

方法一：暴力枚举 + 哈希表

枚举 从每⼀个位置 开始往后，无重复字符的子串可以到达什么位置。找出其中长度最大的即

可。在往后寻找无重复子串能到达的位置时，可以利用「哈希表」统计出字符出现的频次，来判断什么时候子串出现了重复元素

方法二：滑动窗口 + 哈希表：

（1）left = 0, right = 0

- 定义一个数组模拟哈希表来记录每个字符出现的次数。

（2）进窗口

- 每当字符串出现一次时，数组中对应位置大小+1，来记录字符出现的次数

（3）判断什么时候出窗口并更新结果

- hash[s[right]]大于1，那就说明此时字符s[right]与 [left到right) 之间的字符有重复。这时开始移动left（出窗口），并且hash[s[left]]-1，这样当left移动到有重复的字符并-1时，循环结束。开始更新结果。

- hash[s[right]]没有超过1，则说明没有窗口间重符字符，更新结果，继续移动窗口right++

三、代码实现

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[128] = { 0 };int left = 0, right = 0, n = s.size();int ret = 0;while (right < n){hash[s[right]]++;while (hash[s[right]] > 1)hash[s[left++]]--;ret = max(ret, right - left + 1);right++;}return ret;}
};

. - 力扣（LeetCode）

4. 最大连续1的个数|||

一、题目介绍

二、思路解析

这道题可以转换为找到数组中不超过包含k个0的的最长连续区间。既然是连续区间，可以考虑使用「滑动窗口」来解决问题。

滑动窗口：

（1）left = 0, right = 0

- 初始化left，right，zero。

（2）进窗口

- 遍历数组，当该元素是0时，zero++（进窗口）。

（3）判断什么时候出窗口并更新结果

- 如果此时zero大于k，left开始移动（出窗口），直到窗口中的0小于k，循环结束后更新结果。

- zero不大于k，则继续进窗口，不断更新最长连续空间的最大值。

三、代码实现

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0, right = 0, zero = 0;int ret = 0, n = nums.size();while (right < n){if (nums[right] == 0) zero++; //进窗口while (zero > k)if(nums[left++] == 0) zero--;//出窗口ret = max(ret, right - left + 1); //更新结果right++;}return ret;}
};

. - 力扣（LeetCode）

5. 将x减小到零的最小操作

一、题目介绍

二、思路解析

我们可以转化成求数组内⼀段连续的、和为 sum(nums) - x 的最长数组。此时，就是熟悉的「滑动窗口」问题了

滑动窗口 + 哈希表：

（1）left = 0, right = 0

- 定义一个tmp用来存储当前窗口中的数之和，len来存储最长窗口

（2）进窗口

- 当right < n 时，tmp不断的加上当前right位置的值（进窗口）

（3）判断什么时候出窗口并更新结果

- 当窗口中的值tmp大于target时，tmp减去left位置的值，left++（出窗口）。如果窗口重的值等于target则更新结果。

三、代码实现

class Solution {
public:int minOperations(vector<int>& nums, int x) {int left = 0, right = 0;int sum = 0, n = nums.size();for (int& e : nums) sum += e;int target = sum - x;if (target < 0) return -1;else if (target == 0) return n;int tmp = 0, len = -1;while (right < n){ tmp += nums[right];// 入窗口while (tmp > target) tmp -= nums[left++]; //出窗口if (tmp == target) len = max(len, right - left + 1); //更新结果right++;}if (len == -1) return -1;else return n - len;}
};

. - 力扣（LeetCode）

6. 水果成篮

一、题目介绍

注意：0、1、2、3分别表示是一种水果,而不是拥有水果的类型。例如0表示苹果，1表示香蕉，2表示西瓜，3表示鸭梨

二、思路解析

研究的对象是⼀段连续的区间，可以使⽤「滑动窗口」思想来解决问题。

暴力枚举 + 哈希表

枚举将数组中的每一个元素都当做起点开始向后遍历，直到哈希表中的值大于2，比较所有枚举结果中的最大数目

滑动窗口 + 哈希表：

（1）left = 0, right = 0

- 定义一个哈希表用来记录窗口中采摘水果的中类

（2）进窗口

- 每采摘一棵树，该树代表的水果对应哈希表中的位置+1（进窗口）。

（3）判断什么时候出窗口并更新结果

- 当hash的大小大于2时，说明此时窗口中的水果的种类超过了两种，这时开始移动left（出窗口），hash[left]--，当hash[left] 等于0时，说明窗口内没有这种水果了，删除hash表中的该种水果，更新结果。

- 当hash的大小不大于2，说明此时窗口内水果的种类没有超过2，则更新结果，继续进窗口

三、代码实现

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int, int> hash; //统计窗口内出现了几种水果int left = 0, right = 0;int n = fruits.size(), ret = 0;while (right < n){hash[fruits[right]]++; // 进窗口while (hash.size() > 2) //判断{//出窗口hash[fruits[left]]--;if (hash[fruits[left]] == 0)hash.erase(fruits[left]);left++;}ret = max(ret, right - left + 1);//更新结果right++;}return ret;}
};

. - 力扣（LeetCode）

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

一、题目介绍

二、思路解析

- 因为字符串 p 的异位词的长度⼀定与字符串 p 的长度相同，所以我们可以在字符串 s 中构

造⼀个长度为与字符串 p 的长度相同的滑动窗口，并在滑动中维护窗口中每种字母的数量；

- 当窗口中每种字母的数量与字符串 p 中每种字母的数量相同时，则说明当前窗口为字符串 p

的异位词；

- 因此可以用两个大小为 26 的数组来模拟哈希表，⼀个来保存 s 中的子串每个字符出现的个

数，另⼀个来保存 p 中每⼀个字符出现的个数。这样就能判断两个串是否是异位词。

暴力枚举 + 哈希表

枚举字符串中每三个字符和p进行比较。用hash表记录每三个字符的种类和数量，和p进行比较。

滑动窗口 + 哈希表：

（1）left = 0, right = 0

定义两个hash表，一个用来保存 s 中的子串每个字符出现的个数，另⼀个来保存 p 中每⼀个字符出现的个数。再定义一个count用来表示窗口中符合p的异位词的个数

（2）进窗口

- for循环，每循环一次进一次窗口

（3）判断什么时候出窗口并更新结果

- 刚进窗口的字符是p中的异位词，并且此时窗口中该字符的数量小于p中该字符的数量（例如如果刚进窗口中字符是a，p中也有一个a，并且窗口前两个字符都不是a。符合条件），count++，表示窗口中是p中异位词的数量多了一个。如果此时窗口中该字符的数量大于p中该字符的数量，则不符合条件（例如窗口中【a, b, a】，p中【a, b , c】）。

- 刚进窗口中的字符不是p中的异位词，hash2[in- 'a'] <= hash1[in - 'a']也不成立（例如进窗口的字符是d，那么hash2【d - 'a'】 = 1，而p中没有d，那么hash1【d - ‘a’】= 0，定义hash表示，所有元素初始化为0，出现一次+1）

- 当窗口大小大于p的大小时，移动left，此时出窗口的字符如果是p的异位词并且窗口中该字符的数量不多于p中该字符的数量（例如上面的【a, b, a】，当移走第一个a时，hash表中字符a所在位置的大小为2，就不执行count--），count--，窗口中是p的异位词的数量-1，最后hash表中left移动前所在位置-1（出窗口）。

- 当count == p的大小时，说明窗口中都是p的异位词

三、代码实现

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;//统计字符串p中每个字符的个数int hash1[26] = { 0 };for (auto e : p) hash1[e- 'a']++;//统计滑动窗口中中每个字符的个数int hash2[26] = { 0 };int count = 0;for (int left = 0, right = 0; right < s.size(); right++){char in = s[right];hash2[in - 'a']++;//进窗口if (hash2[in- 'a'] <= hash1[in - 'a']) count++;//维护countif (right - left + 1 > p.size()){char out = s[left++];if (hash2[out - 'a'] <= hash1[out - 'a']) count--;//维护counthash2[out - 'a']--;//出窗口}//更新结果if (count == p.size()) ret.push_back(left);}return ret;}
};

. - 力扣（LeetCode）

8. 串联所有单词的子串

一、题目介绍

二、思路解析

如果我们把每⼀个单词看成⼀个⼀个字母，问题就变成了找到「字符串中所有的字母异位词」。无

非就是之前处理的对象是⼀个⼀个的字符，我们这里处理的对象是⼀个⼀个的单词。小伙伴们可以照着上题的思路自己想一想做一做，做题思路这里不再赘述。

. - 力扣（LeetCode）

三、代码实现

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;//跑存words中所有字符串的个数unordered_map<string, int> hash1;for (auto& st: words) hash1[st]++;int n = words[0].size(), m = words.size();for (int i = 0; i < n; i++){unordered_map<string, int> hash2;for(int left = i, right = i, count = 0; right + n <= s.size(); right += n){string in = s.substr(right, n);hash2[in]++;// 入窗口if (hash1[in] && hash2[in] <= hash1[in]) count++;// 维护count//判断if (right - left + 1 > n * m) {string out = s.substr(left, n);if (hash1[out] && hash2[out] <= hash1[out]) count--;// 维护counthash2[out]--;//出窗口left += n;}if (count == m) ret.push_back(left);}}return ret;}
};

9. 最小覆盖子串

一、题目介绍

二、思路解析

研究对象是连续的区间，因此可以尝试使用滑动窗口的思想来解决。

如何判断当前窗口内的所有字符是符合要求的呢？

- 我们可以使用两个哈希表，其中⼀个将目标串的信息统计起来，另⼀个哈希表动态的维护窗口

内字符串的信息。

- 当动态哈希表中包含目标串中所有的字符，并且对应的个数都不小于目标串的哈希表中各个字

符的个数，那么当前的窗口就是⼀种可行的方案。

暴力枚举 + 哈希表

枚举从中的每个字符开始向后遍历数组，直到找到覆盖t的位置，比较枚举的所有结果选取最小值。

滑动窗口 + 哈希表：

（1）left = 0, right = 0

定义两个hash表⼀个将目标串的信息统计起来，另⼀个哈希表动态的维护窗口内字符串的信息。定义一个kind，统计目标传中字符的种类。定义count统计窗口中能够覆盖t的字符种类的数量。

（2）进窗口

for循环，进窗口

（3）判断什么时候出窗口和更新结果

- 只有当窗口中的某一字符数等于t中的该字符的个数时，count才会+1（例如t中有两个A，那么只有窗口中出现第二个A时，才会执行count++，第一个A出现时不会执行count++）。

- 当count == kind时，说明此时窗口可以覆盖字符串t，更新结果，记录下此时窗口的起始位置和窗口的长度。然后判断是否count--，移动left，hash[left]--（出窗口）。

三、代码实现

class Solution {
public:string minWindow(string s, string t) {string ret;int hash1[128] = { 0 };// 统计t中每个字符出现的次数int kinds = 0; // 统计t中字符的种类for (auto& e : t) if ( hash1[e]++ == 0 ) kinds++;int hash2[128] = { 0 }; // 统计s中每个字符出现的次数int n = s.size(), m = t.size();int minlen = INT_MAX, begin = -1;for (int left = 0, right = 0, count = 0; right < n; right++){char in = s[right];hash2[in]++; // 入窗口if (hash2[in] == hash1[in]) count++;//维护countwhile (count == kinds){if (right - left + 1 < minlen)//更新结果{minlen = right - left + 1;begin = left;}char out = s[left++];if (hash2[out] == hash1[out]) count--;//维护counthash2[out]--;//出窗口}}if (begin == -1) return "";else return s.substr(begin, minlen);}
};

. - 力扣（LeetCode）

1. 滑动窗口简介

2. 长度最小的子数组

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

4. 最大连续1的个数|||

5. 将x减小到零的最小操作

6. 水果成篮

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

8. 串联所有单词的子串

9. 最小覆盖子串

相关文章：