深入理解滑动窗口算法及其经典应用

在算法设计中，滑动窗口是一种高效的技巧，尤其在处理连续子数组或子串问题时非常有用。滑动窗口的核心思想是使用两个指针，定义一个范围，在这个范围内计算所需的值，然后根据问题的要求移动窗口的边界。本文将详细剖析几道经典题目，结合代码来讲解滑动窗口的原理和应用。

什么是滑动窗口？

滑动窗口技术通常用于解决子数组或子串相关的问题。其主要思想是在数组或字符串上维持一个固定的窗口大小，或在特定条件下调整窗口大小，从而在窗口内进行高效的计算。滑动窗口技术可以帮助我们在O(n)的时间复杂度内解决一些需要遍历整个数组或字符串的问题。
滑动窗口的基本步骤包括：

1. 初始化窗口的左右边界（通常为两个指针）。
2. 移动窗口的右边界扩展窗口范围，直至满足某些条件。
3. 移动窗口的左边界收缩窗口，直至不再满足条件。
4. 记录或更新需要的结果。

接下来，我们通过几道经典的滑动窗口问题，来深入理解这一技巧的应用。

经典题型分析与讲解

1. 长度最小的子数组

题目描述：
给定一个含有n个正整数的数组和一个正整数**target**，找出该数组中满足其和大于等于**target**的长度最小的连续子数组，并返回其长度。如果不存在符合条件的子数组，返回0。
滑动窗口思路：

1. 我们使用两个指针**left**和**right**表示窗口的左右边界。
2. 初始时两个指针都指向数组的起点。
3. 扩展**right**指针，使窗口内的数字和逐渐增大。
4. 当窗口内的和大于等于**target**时，收缩**left**指针以找到最小的子数组长度。
5. 在整个过程中，动态更新最小长度。

class Solution {
public:int minSubArrayLen(int target, vector<int>& nums) {int left = 0;int right = 0;int len = INT_MAX;  // 初始化最小子数组长度为无穷大int n = nums.size();int sum = 0;  // 当前窗口的数字和// 遍历数组，扩展右边界for (; right < n; right++) {sum += nums[right];  // 将当前右边界的数字加入窗口的和中// 当窗口内的和大于或等于目标值时，缩小窗口while (sum >= target) {len = min(len, right - left + 1);  // 更新最小子数组长度sum -= nums[left];  // 减去左边界的数字，将窗口左边界右移left++;}}// 如果找不到符合条件的子数组，返回0；否则返回最小长度return len == INT_MAX ? 0 : len;}
};

复杂度分析：

• 时间复杂度：O(n)，其中n为数组的长度。每个元素在扩展和收缩窗口的过程中最多只会被访问两次。
• 空间复杂度：O(1)，仅使用了常数个额外空间。

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

题目描述：
给定一个字符串**s**，请你找出其中不含有重复字符的最长子串的长度。
滑动窗口思路：

1. 使用一个哈希表**hash**来记录窗口内字符的频率。
2. 移动**right**指针扩展窗口，加入字符到哈希表中。
3. 如果窗口内出现重复字符，则移动**left**指针收缩窗口，直到不再有重复字符。
4. 在整个过程中，动态更新最大子串长度。

class Solution {
public:int lengthOfLongestSubstring(string s) {int hash[200] = { 0 };  // 用于记录字符的频率int left = 0;int right = 0;int ret = 0;while (right < s.size()) {hash[s[right]]++;// 当出现重复字符时，收缩窗口while (hash[s[right]] > 1) {hash[s[left++]]--;}// 更新最长子串长度ret = max(ret, right - left + 1);right++;}return ret;}
};

复杂度分析：

• 时间复杂度：O(n)，字符串的每个字符最多访问两次。
• 空间复杂度：O(1)，哈希表的大小为固定的常数级。

3. 最长重复子数组

题目描述：
给定一个二进制数组**nums**和一个整数**k**，如果可以将最多**k**个**0**变成**1**，求最长的连续**1**的长度。
滑动窗口思路：

1. 使用两个指针**left**和**right**表示滑动窗口。
2. 每次扩展**right**指针，将遇到的**0**记录在计数器**counter**中。
3. 当窗口内**0**的个数大于**k**时，收缩窗口，直到**0**的个数不超过**k**。
4. 在整个过程中，动态更新最大连续**1**的长度。

class Solution {
public:int longestOnes(vector<int>& nums, int k) {int left = 0;int right = 0;int ret = 0;int counter = 0;  // 记录窗口内0的个数for (; right < nums.size(); ++right) {if (nums[right] == 0) counter++;  // 遇到0则计数器加1// 当窗口内0的个数超过k时，收缩窗口while (counter > k) {if (nums[left] == 0) counter--;left++;}// 更新最大长度ret = max(ret, right - left + 1);}return ret;  // 返回最大长度}
};

复杂度分析：

• 时间复杂度：O(n)，数组的每个元素最多访问两次。
• 空间复杂度：O(1)，仅使用了常数个额外空间。

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

题目描述：
给定一个整数数组**nums**和一个整数**x**，你可以从数组的开头或者末尾取元素来减小**x**。请你返回最少需要多少次操作才能将**x**减少到**0**，如果无法实现，返回**-1**。
滑动窗口思路：

1. 计算数组总和**sum**，目标是找到一个和为**sum - x**的最长子数组。
2. 使用滑动窗口来找这个最长的子数组。
3. 如果找到了目标子数组，则返回最少操作数，即**nums.size() - 最大子数组长度**。
4. 否则返回**-1**。

class Solution {
public:int minOperations(vector<int>& nums, int x) {int sum = accumulate(nums.begin(), nums.end(), 0);  // 计算数组总和int target = sum - x;  // 目标是找和为 sum - x 的子数组if (target < 0) return -1;  // 如果目标和为负数，直接返回-1if (target == 0) return nums.size();  // 如果目标和为0，返回整个数组长度int ret = 0, tmp = 0;for (int left = 0, right = 0; right < nums.size(); right++) {tmp += nums[right];// 当 tmp 大于目标值时，缩小窗口while (tmp > target) {tmp -= nums[left];left++;}// 找到一个和为 target 的子数组，更新 retif (tmp == target) ret = max(ret, right - left + 1);}// 返回最少操作数return ret == 0 ? -1 : nums.size() - ret;}
};

复杂度分析：

• 时间复杂度：O(n)，数组的每个元素最多访问两次。
• 空间复杂度：O(1)，仅使用了常数个额外空间。

5. 水果成篮 (LeetCode 904)

题目描述：
在一条树木组成的行上，有 n 棵树，每棵树上都挂着不同种类的水果。你只有两个篮子，每个篮子只能装一种类型的水果。你需要尽可能多地收集水果，但每次只能从连续的树上收集。
滑动窗口思路：
这道题可以看作是一个典型的滑动窗口问题，要求在一个数组中找到最多包含两个不同元素的最长子数组。我们通过滑动窗口来动态地调整当前子数组的左右边界，以找到满足条件的最长子数组。
代码分析：

class Solution {
public:int totalFruit(vector<int>& fruits) {unordered_map<int, int> basket; // 用于记录每种水果的数量int max_fruits = 0; // 记录最多的水果数量int left = 0; // 窗口的左边界// 右边界从0开始移动for (int right = 0; right < fruits.size(); ++right) {basket[fruits[right]]++; // 将当前水果加入到篮子中// 如果篮子中的水果种类超过两种，调整左边界while (basket.size() > 2) {basket[fruits[left]]--; // 移除左边界的水果if (basket[fruits[left]] == 0) {basket.erase(fruits[left]); // 种类数量为0时移除该种类}left++; // 移动左边界}// 更新最大水果数量max_fruits = max(max_fruits, right - left + 1);}return max_fruits; // 返回结果}
};

详细解读：

1. 初始化与边界控制：basket 是一个哈希表，用于记录当前窗口中每种水果的数量。left 是窗口的左边界，right 是窗口的右边界。
2. 窗口扩展：通过 right 指针逐渐扩展窗口，将当前水果加入到篮子中。
3. 窗口收缩：如果篮子中的水果种类超过两种，开始通过 left 指针收缩窗口，直到篮子中只有两种或更少种类的水果。
4. 结果更新：每次调整窗口后，计算当前窗口的长度，并更新 max_fruits，以记录目前为止可以收集的最多水果数量。
5. 返回结果：遍历整个数组后，max_fruits 中记录的就是最多的连续水果数量。

6. 滑动窗口最大值 (LeetCode 239)

题目描述：
给定一个数组 nums 和滑动窗口大小 k，请找出所有滑动窗口里的最大值。
滑动窗口 + 双端队列思路：
这道题的难点在于如何在每次滑动窗口移动时，快速找到当前窗口的最大值。我们可以借助一个双端队列 deque 来解决这个问题。deque 中保存的是元素在数组中的索引，并且这些索引对应的元素值在 deque 中是从大到小排列的。
代码分析：

class Solution {
public:vector<int> maxSlidingWindow(vector<int>& nums, int k) {deque<int> dq;  // 存储数组元素的索引vector<int> result;for (int i = 0; i < nums.size(); i++) {// 移除不在窗口范围内的元素if (!dq.empty() && dq.front() < i - k + 1) {dq.pop_front();}// 移除队列中比当前元素小的元素while (!dq.empty() && nums[dq.back()] <= nums[i]) {dq.pop_back();}dq.push_back(i);  // 将当前元素的索引添加到队列// 当窗口大小达到 k 时，记录当前窗口的最大值if (i >= k - 1) {result.push_back(nums[dq.front()]);}}return result;}
};

详细解读：

1. 初始化队列与结果数组：deque 用于存储数组元素的索引，result 存储最终的最大值。
2. 维护双端队列：在遍历 nums 时，首先检查 deque 的头部索引是否在当前窗口外，如果在则移除。然后，移除 deque 中所有比当前元素小的元素，因为这些元素不可能成为当前窗口的最大值。
3. 记录结果：当窗口的大小达到 k 时，deque 的头部元素就是当前窗口的最大值，将其添加到 result 中。
4. 返回结果：遍历完成后，返回 result，其中存储了每个滑动窗口的最大值。

7. 字符串中的所有字母异位词 (LeetCode 剑指 Offer II 015)

题目描述：
给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。
滑动窗口思路：
这道题与滑动窗口的使用密切相关，我们通过一个滑动窗口来逐步遍历字符串 s，同时维护一个与字符串 p 的字符频率相匹配的哈希表，以此来判断当前窗口是否为 p 的字母异位词。
代码分析：

class Solution {
public:vector<int> findAnagrams(string s, string p) {vector<int> ret;  // 存储结果的向量int hash1[26] = { 0 };  // 存储字符串 p 中字符的频率// 计算字符串 p 中每个字符的频率for (auto ch : p)hash1[ch - 'a']++;int hash2[26] = { 0 };  // 存储当前滑动窗口中字符的频率int left = 0, count = 0;for (int right = 0; right < s.size(); right++) {char in = s[right];hash2[in - 'a']++;if (hash2[in - 'a'] <= hash1[in - 'a'])count++;// 当窗口长度超过字符串 p 的长度时，调整窗口if (right - left + 1 > p.size()) {char out = s[left];if (hash2[out - 'a']-- <= hash1[out - 'a'])count--;left++;}// 如果 count 等于 p 的长度，说明找到一个字母异位词if (count == p.size())ret.push_back(left);}return ret;}
};

详细解读：

1. 哈希表初始化：hash1 存储字符串 p 中每个字符的频率。
2. 窗口扩展：right 指针逐步扩展窗口，将当前字符添加到 hash2 中，并检查是否符合 p 的字符频率。
3. 窗口收缩：当窗口大小超过 p 的长度时，调整 left 指针，移除最左边的字符，并更新 hash2 中的频率。
4. 结果记录：如果当前窗口中符合 p 的所有字符频率，则记录当前窗口的起始位置。
5. 返回结果：最终返回 ret，其中存储了所有符合条件的起始索引。

8. 串联所有单词的子串 (LeetCode 30)

题目描述：
给定一个字符串 s 和一个字符串数组 words，找出 s 中所有可以由 words 中所有单词串联形成的子串的起始位置。
滑动窗口思路：
这道题可以看作是将每个单词视为一个单位的滑动窗口问题，我们需要找到一个窗口，使得其中包含 words 中的所有单词，并且每个单词出现的次数都与 words 中的频率一致。
代码分析：

class Solution {
public:vector<int> findSubstring(string s, vector<string>& words) {vector<int> ret;unordered_map<string, int> hash1;  // 保存 words 里面所有单词的频次// 统计 words 中每个单词的出现次数for (auto& word : words)hash1[word]++;int len = words[0].size();  // 单词的长度int m = words.size();  // 单词的数量// 执行 len 次（从不同的起点开始）for (int i = 0; i < len; i++) {unordered_map<string, int> hash2;  // 维护窗口内单词的频次for (int left = i, right = i, count = 0; right + len <= s.size(); right += len) {// 进窗口并维护 countstring in = s.substr(right, len);hash2[in]++;if (hash2[in] <= hash1[in])  count++;// 判断窗口大小是否超过了允许的大小，进行出窗口操作并维护 countif (right - left + len > len * m) {string out = s.substr(left, len);if (hash2[out] <= hash1[out]) count--;hash2[out]--;left += len;}// 更新结果，如果当前窗口内的单词数量和 words 中一致，记录左边界if (count == m)  ret.push_back(left);}}return ret;}
};

详细解读：

1. 哈希表初始化：hash1 用于存储 words 中每个单词的频率。
2. 窗口扩展：right 指针逐步扩展窗口，将当前单词添加到 hash2 中，并检查是否符合 words 中的频率。
3. 窗口收缩：如果当前窗口大小超过了 words 中所有单词串联后的长度，则调整 left 指针，移除最左边的单词，并更新 hash2。
4. 结果记录：当 count 等于 words 的长度时，说明当前窗口符合要求，将窗口的起始位置 left 记录到 ret 中。
5. 返回结果：最终返回 ret，其中存储了所有符合条件的起始索引。

9. 最小覆盖子串 (LeetCode 76)

题目描述：
给定一个字符串 s 和一个字符串 t，找到 s 中包含 t 的所有字符的最小子串。
滑动窗口思路：
我们需要维护一个滑动窗口，使得窗口中的子串包含 t 的所有字符，且窗口尽可能小。
代码分析：

class Solution {
public:string minWindow(string s, string t){int hash1[128] = { 0 };int kinds = 0;// 初始化hash1，计算需要匹配的字符种类数kindsfor (auto a : t){if (hash1[a] == 0) kinds++;hash1[a]++;}int hash2[128] = { 0 };int begin = -1;  // 用于记录最小子串的起始位置：int begin = -1;  // 用于记录最小子串的起始位置int min_len = INT_MAX;  // 记录最小子串长度for (int left = 0, right = 0, count = 0; right < s.size(); ++right){char in = s[right];hash2[in]++;// 如果当前字符频率与目标频率匹配，增加countif (hash2[in] == hash1[in]) count++;// 当所有字符频率都匹配时，开始尝试缩小窗口while (count == kinds){// 更新最小子串的起始位置和长度if (right - left + 1 < min_len){min_len = right - left + 1;begin = left;}char out = s[left];left++;// 移出左边界字符后，判断是否需要减少countif (hash2[out] == hash1[out]) count--;hash2[out]--;}}// 如果没有找到满足条件的子串，返回空字符串if (begin == -1) return "";return s.substr(begin, min_len);}
};

详细解读：

1. 初始化哈希表：hash1 用于记录字符串 t 中每个字符的频率，并计算需要匹配的字符种类数 kinds。hash2 用于记录当前窗口中字符的频率。
2. 窗口扩展：right 指针逐步扩展窗口，将当前字符添加到 hash2 中。如果当前字符在 hash2 中的频率与 hash1 中的频率相同，则增加 count。
3. 窗口收缩：当 count 等于 kinds 时，意味着当前窗口已经包含了 t 中的所有字符，此时尝试缩小窗口。如果缩小后的窗口仍然包含 t 中的所有字符，则更新最小子串的起始位置和长度。
4. 判断结果：如果最终找到了符合条件的子串，返回该子串，否则返回空字符串。

总结

上述算法都使用了滑动窗口技术来解决问题。滑动窗口的核心思想是逐步扩展窗口，同时保持窗口的最优状态，尽可能减少不必要的计算。通过维护一个哈希表来记录窗口内的字符频率或单词频率，可以有效地判断当前窗口是否满足题目要求。每当窗口状态符合要求时，记录当前的结果，并尝试收缩窗口以找到更优解。