【优选算法篇】编织算法的流动诗篇：滑动窗口的轻盈之美

半截诗

发布于 2024-10-20 08:12:37

5920

文章被收录于专栏：学西学西

C++ 滑动窗口详解：基础题解与思维分析

💬 欢迎讨论：如有疑问或见解，欢迎在评论区留言互动。 👍 点赞、收藏与分享：如觉得这篇文章对您有帮助，请点赞、收藏并分享！ 🚀 分享给更多人：欢迎分享给更多对 C++ 感兴趣的朋友，一起学习滑动窗口的基础与进阶！

前言

滑动窗口是一种常用的算法技巧，主要用于处理子数组、子串等具有“窗口”特性的题目。在本篇博客中，我们将通过具体的例题讲解，深入剖析滑动窗口的思想和它的应用场景。滑动窗口法能够在保持高效计算的同时，减少重复的工作，因而在处理某些连续区间问题时，常常是最优解法。

第一章：热身练习

1.1 长度最小的子数组

题目链接：209. 长度最小的子数组 题目描述：给定一个含有 n 个正整数的数组 nums 和一个正整数 target。找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0。

示例 1：

输入：target = 7, nums = [2, 3, 1, 2, 4, 3]
输出：2
解释：子数组 [4, 3] 是该条件下的长度最小的子数组。

示例 2：

输入：target = 4, nums = [1, 4, 4]
输出：1

示例 3：

输入：target = 11, nums = [1, 1, 1, 1, 1, 1, 1, 1]
输出：0

解法一（暴力求解）

算法思路：

通过枚举数组中的所有子数组，计算它们的和，并检查是否大于等于 target，从中找出符合条件的最小子数组。暴力解法虽然简单直接，但在处理大规模数据时效率较低，容易超时。

具体步骤：

枚举数组中的所有子数组。
计算每个子数组的和。
如果子数组的和大于等于 target，记录其长度，并在所有子数组中找出最小的长度。

代码实现：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int n = nums.size();
        int result = INT_MAX;
        
        for (int start = 0; start < n; ++start) {
            int sum = 0;
            for (int end = start; end < n; ++end) {
                sum += nums[end];
                if (sum >= target) {
                    result = min(result, end - start + 1);
                    break;
                }
            }
        }
        return result == INT_MAX ? 0 : result;
    }
};

复杂度分析：

时间复杂度：O(n^2)，需要枚举所有可能的子数组。
空间复杂度：O(1)，仅使用常量级的额外空间。

暴力求解的缺点：

对于大数据集（如 10^5 级别），该方法会导致时间超限。我们需要一种更高效的算法来解决这个问题。

解法二（滑动窗口）

算法思路：

滑动窗口是一种高效的解决方法，它通过两个指针 left 和 right，动态调整窗口的大小来找到满足条件的最短子数组。具体过程如下：

初始化 left 和 right，从数组左端开始。
将 right 向右移动，扩大窗口，并计算窗口内元素的和。
如果窗口内的和 ≥ target，尝试收缩窗口，即将 left 向右移动，尽可能缩小窗口，并更新最小子数组的长度。
重复上述过程，直到 right 遍历完整个数组。

代码实现：

class Solution {
public:
    int minSubArrayLen(int target, vector<int>& nums) {
        int left = 0, sum = 0, result = INT_MAX;
        
        for (int right = 0; right < nums.size(); ++right) {
            sum += nums[right];
            while (sum >= target) {
                result = min(result, right - left + 1);
                sum -= nums[left++];
            }
        }
        return result == INT_MAX ? 0 : result;
    }
};

复杂度分析：

时间复杂度：O(n)，每个元素最多被访问两次（一次是加入窗口，一次是移出窗口）。
空间复杂度：O(1)，只使用了固定的额外空间。

滑动窗口的核心思想

滑动窗口法通过调整窗口的大小来找到满足条件的最优解。当窗口内元素的和大于等于 target 时，我们尝试缩小窗口，这样可以找到满足条件的最短子数组。

图解分析

假设 target = 7, nums = [2, 3, 1, 2, 4, 3]：

初始状态：left = 0, right = 0, sum = 2，窗口未达到 target。
扩大窗口：将 right 向右移动，直到窗口和 sum = 9，满足条件。
缩小窗口：移动 left，将子数组 [4, 3] 缩小到长度 2。

步骤图解：

Iteration	Left	Right	Sum	Subarray	Result
1	0	3	8	[2, 3, 1, 2]	4
2	1	3	6	[3, 1, 2]	4
3	1	4	10	[3, 1, 2, 4]	4
4	2	4	7	[1, 2, 4]	3
5	3	4	6	[2, 4]	3
6	3	5	9	[2, 4, 3]	3
7	4	5	7	[4, 3]	2

图解说明：

Iteration 1：从左端 left = 0，右端扩展到 right = 3，子数组 [2, 3, 1, 2] 的和为 8，大于 target，记录最小长度为 4。
Iteration 2：缩小窗口，将 left 右移到 1，新窗口和为 6，小于 target，不更新结果。
Iteration 3：右端扩展到 4，子数组和为 10，更新最小长度为 4。
Iteration 4：继续缩小窗口，将 left 右移到 2，子数组 [1, 2, 4] 的和为 7，更新最小长度为 3。
Iteration 5：left 再次右移，和降到 6，小于 target，不更新结果。
Iteration 6：right 扩展到 5，子数组 [2, 4, 3] 的和为 9，不更新最小长度。
Iteration 7：最后，left 移到 4，子数组 [4, 3] 的和为 7，最终更新最小长度为 2。

滑动窗口的有效性

滑动窗口是一种高效的算法思想，特别适用于处理子数组和子串等问题。下面详细解释其原理以及为何时间复杂度较低：

滑动窗口的核心思想 滑动窗口寻找的是：以当前窗口最左侧元素（记为 left1）为基准，找出从 left1 开始满足条件的区间，也就是使得子数组的和 sum 大于等于 target 时的最右侧（记为 right1）。在这道题中，当 sum >= target 时，说明从 left1 到 right1 的子数组满足条件，并且我们可以记录这个窗口的长度。
避免重复计算 当我们已经找到从 left1 开始的最优区间后，left1 就可以被舍弃。此时如果继续像暴力解法那样重新从 left2 开始计算后续的子数组和，会导致大量重复的计算。因为从 left1 到 right1 的区间中，许多元素的和已经被计算过了，我们可以充分利用这个已有的信息。
优化窗口的移动 此时，right1 的作用就显现出来了。通过滑动窗口，我们不需要重新计算新的区间，而是将 left1 从窗口内移除（即从 sum 中减去 left1 对应的值）。然后，我们直接从 right1 开始，继续向右扩展 right 来寻找下一个满足条件的区间（即 left2 开始的最短区间）。这样，当 sum >= target 的条件不再满足时，我们再次缩小窗口，从而达到寻找最优解的目的。
高效性 滑动窗口法使得我们可以避免重新从头计算每个子数组的和。每当一个区间满足条件时，我们就可以通过缩小窗口来检查是否有更短的区间可以满足条件。通过这种滑动的方式，我们不仅能解决问题，还大幅减少了重复计算，从而提高了算法效率。

核心就是：left和right指针不会回退！！！也称为同向指针

时间复杂度分析

滑动窗口虽然看起来有两层循环（外层控制 right 的扩展，内层控制 left 的缩小），但实际上每个指针（left 和 right）最多只会遍历数组 n 次。

right 指针：从左向右遍历整个数组，每个元素最多只被访问一次。
left 指针：每当 sum >= target 时，left 会右移以缩小窗口，每个元素也最多只会被访问一次。

因此，left 和 right 指针都是单调递增的，不会回退，二者在整个过程中最多各自移动 n 次，最终的时间复杂度为 O(n)。

易错点提示

窗口的收缩条件：当窗口内的和 ≥ target 时，我们才能缩小窗口。
窗口最小长度的更新：每次缩小窗口时，都要更新最小长度，否则可能遗漏最优解。

1.2 无重复字符的最长子串

题目链接：3. 无重复字符的最长子串 题目描述：给定一个字符串 s ，请你找出其中不含有重复字符的最长子串的长度。

示例 1：

输入：s = "abcabcbb"
输出：3
解释：因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2：

输入：s = "bbbbb"
输出：1
解释：因为无重复字符的最长子串是 "b"，所以其长度为 1。

示例 3：

输入：s = "pwwkew"
输出：3
解释：因为无重复字符的最长子串是 "wke"，所以其长度为 3。请注意，答案必须是子串的长度，"pwke" 是一个 子序列，不是子串。

提示：

0 <= s.length <= 5 * 10^4
s 由英文字母、数字、符号和空格组成

解法一（暴力求解）

算法思路：

通过枚举从每个位置开始，向后寻找无重复字符的子串能到达的位置，记录其中最长的子串长度即可。在寻找无重复子串时，可以使用哈希表统计字符出现的频次，遇到重复字符时停止。

具体步骤：

枚举每个起始位置 i，从该位置开始寻找最长的无重复子串。
使用哈希表统计字符出现的频次，一旦出现重复字符，终止当前枚举。
更新最长无重复子串的长度。
返回结果。

代码实现：

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        int ret = 0;  // 记录结果
        int n = s.length();
        
        // 枚举从不同位置开始的无重复子串
        for (int i = 0; i < n; i++) {
            int hash[128] = { 0 };  // 记录字符频次
            for (int j = i; j < n; j++) {
                hash[s[j]]++;  // 统计字符频次
                if (hash[s[j]] > 1)  // 出现重复，终止
                    break;
                ret = max(ret, j - i + 1);  // 更新结果
            }
        }
        return ret;
    }
};

复杂度分析：

时间复杂度：O(n^2)，枚举每个起点，并从该起点向后查找无重复字符的子串。
空间复杂度：O(1)，只需常量空间存储字符频次。

缺点：

对于大数据集（如 10^5 级别），该算法会超时，因此需要一种更高效的解法。

解法二（滑动窗口）

算法思路：

滑动窗口是一种高效解决子串问题的方式。使用滑动窗口法时，维持一个窗口，使得窗口内的所有字符都是不重复的。当窗口右端进入新字符时，更新哈希表记录字符频次：

如果字符频次大于 1，则窗口内出现了重复字符，开始从左侧缩小窗口，直到频次恢复为 1。
如果没有重复字符，直接更新最长无重复子串的长度。

代码实现：

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;
    }
};

复杂度分析：

时间复杂度：O(n)，每个字符最多被左右指针访问两次，因此时间复杂度为线性。
空间复杂度：O(1)，只需常量空间存储字符频次。

图解分析

假设 s = "abcabcbb"，滑动窗口的执行过程如下：

Iteration	Left	Right	Hash Table	Substring	Length (Result)
1	0	0	a:1	“a”	1
2	0	1	a:1, b:1	“ab”	2
3	0	2	a:1, b:1, c:1	“abc”	3
4	0	3	a:2, b:1, c:1 → 左移 left=1	“bca”	3
5	1	4	b:2, c:1, a:1 → 左移 left=2	“cab”	3
6	2	5	b:1, c:2, a:1 → 左移 left=3	“abc”	3
7	3	6	b:2, c:1 → 左移 left=5	“cb”	3
8	5	7	b:2 → 左移 left=6	“b”	3

详细说明：

Iteration 1：
- Left=0，Right=0，加入字符 a，哈希表为 a:1，当前子串为 "a"，长度为 1。
Iteration 2：
- Right=1，加入字符 b，哈希表为 a:1, b:1，当前子串为 "ab"，长度为 2。
Iteration 3：
- Right=2，加入字符 c，哈希表为 a:1, b:1, c:1，当前子串为 "abc"，长度为 3。
Iteration 4：
- Right=3，加入字符 a，哈希表更新为 a:2, b:1, c:1。由于字符 a 出现两次，移动 Left 指针到 1，此时子串变为 "bca"，长度仍然是 3。
Iteration 5：
- Right=4，加入字符 b，哈希表更新为 b:2, c:1, a:1。由于字符 b 出现两次，移动 Left 到 2，子串变为 "cab"，长度保持为 3。
Iteration 6：
- Right=5，加入字符 c，哈希表更新为 b:1, c:2, a:1。此时字符 c 出现两次，需要再次移动 Left，将 Left 移到 3，此时子串变为 "abc"，长度为 3。
Iteration 7：
- Right=6，加入字符 b，哈希表更新为 b:2, c:1。由于 b 出现两次，移动 Left 到 left=5，此时子串应为 "cb"，长度为 2。
Iteration 8：
- Right=7，继续加入字符 b，哈希表更新为 b:2，再次出现重复字符，移动 Left 到 6，子串为 "b"，长度为 2。

1.3 最大连续 1 的个数 III

题目链接：1004. 最大连续 1 的个数 III 题目描述：给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0，则返回数组中 连续 1 的最大个数。

示例 1：

输入：nums = [1,1,1,0,0,0,1,1,1,1,0], K = 2
输出：6
解释：翻转红色标记的 0 变为 1，最长的子数组长度为 6。 [1,1,1,0,0,1,1,1,1,1]

示例 2：

输入：nums = [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K = 3
输出：10
解释：翻转红色标记的 0 变为 1，最长的子数组长度为 10。 [0,0,1,1,1,1,1,1,1,1,1,1]

解法（滑动窗口）

算法思路：这道题可以简化为求解一段 连续的 1 中包含最多 k 个 0 的最长子数组。由于这个子数组是 连续区间，因此可以使用滑动窗口来解决。

具体步骤：

初始化左右指针 left 和 right，以及记录窗口内 0 的个数的变量 zero。
当 right 指针向右扩展时：
- 如果当前元素是 0，增加 zero 计数。
- 如果 zero 超过了 k，需要通过移动 left 指针来移出窗口内的 0，直到 zero 恢复到不超过 k 的状态。
在窗口合法时，更新最大长度 ret。
循环结束后，ret 保存的即为最大连续 1 的长度。

代码实现：

class Solution {
public:
    int longestOnes(vector<int>& nums, int k) {
        int ret = 0;
        for (int left = 0, right = 0, zero = 0; right < nums.size(); right++) {
            if (nums[right] == 0) zero++;  // 窗口内增加一个 0
            // 如果 0 的数量超过 k，移动 left 指针
            while (zero > k) {
                if (nums[left++] == 0) zero--;  // 窗口左边界收缩，减少一个 0
            }
            // 更新最大长度
            ret = max(ret, right - left + 1);
        }
        return ret;
    }
};

复杂度分析：

时间复杂度：O(n)，每个元素最多被左右指针访问两次（一次进入窗口，一次被移出窗口）。
空间复杂度：O(1)，只使用了几个固定的额外变量存储当前状态。

滑动窗口的核心思想

滑动窗口方法通过不断扩展和收缩窗口来保证窗口内的 0 不超过 k。当窗口内的 0 超过 k 时，移动左边界 left，保持窗口内的 0 不超过 k。在每次移动时，记录下窗口的最大长度。

图解分析

假设 nums = [1,1,1,0,0,0,1,1,1,1,0]，K=2，以下是滑动窗口的执行过程：

步骤图解：

Iteration	Left	Right	Zero Count	Subarray	Length (Result)
1	0	0	0	[1]	1
2	0	1	0	[1, 1]	2
3	0	2	0	[1, 1, 1]	3
4	0	3	1	[1, 1, 1, 0]	4
5	0	4	2	[1, 1, 1, 0, 0]	5
6	0	5	3	[1, 1, 1, 0, 0, 0]	5
7	4	5	2	[0, 0]	5
8	4	6	2	[0, 0, 1]	5
9	4	7	2	[0, 0, 1, 1]	5
10	4	8	2	[0, 0, 1, 1, 1]	5
11	4	9	2	[0, 0, 1, 1, 1, 1]	6
12	4	10	3	[0, 0, 1, 1, 1, 1, 0]	6
13	5	10	2	[0, 1, 1, 1, 1, 0]	6

详细说明：

Iteration 1-3：从 Right=0 到 Right=2，我们持续遇到 1，所以窗口扩展，Zero Count 仍为 0，子数组 [1,1,1] 长度逐渐增加到 3。
Iteration 4：Right=3，遇到一个 0，Zero Count=1，但还在 k=2 的允许范围内，子数组 [1,1,1,0] 长度为 4。
Iteration 5：Right=4，再遇到一个 0，Zero Count=2，此时子数组 [1,1,1,0,0] 满足条件，长度增加到 5。
Iteration 6：Right=5，再遇到一个 0，Zero Count=3，超出 k=2 的限制。因此需要缩小窗口，Left 开始向右移动。最终 Left 移动到 4，窗口变为 [0, 0]，Zero Count 恢复到 2，子数组长度保持为 5。
Iteration 7-10：Right 不断扩展，子数组逐渐变为 [0,0,1,1,1]，虽然 Zero Count 始终为 2，但最大长度仍为 5。
Iteration 11：Right=9，加入一个 1，窗口变为 [0,0,1,1,1,1]，满足 Zero Count=2，子数组长度增加到 6。
Iteration 12-13：Right=10，遇到一个 0，Zero Count=3，再次超过限制，因此移动 Left，直到 Left=5，窗口变为 [0, 1, 1, 1, 1, 0]，最大长度仍为 6。

关键点：

每次当 0 的数量超过 k 时，我们通过移动 left 指针来缩小窗口，直到窗口内的 0 的数量不超过 k。当窗口合法时，不断更新最长子数组的长度。

1.4 将 x 减到 0 的最小操作数

题目链接：1658. 将 x 减到 0 的最小操作数

题目描述：给你一个整数数组 nums 和一个整数 x。每次操作时，你可以移除数组 nums 的最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，你需要修改数组以供接下来的操作使用。如果可以将 x 恰好减到 0，返回最少的操作数；否则，返回 -1。

示例 1：

输入：nums = [1,1,4,2,3], x = 5
输出：2
解释：最佳解决方案是移除数组末尾的两个元素 [2,3]，将 x 减为 0。

示例 2：

输入：nums = [5,6,7,8,9], x = 4
输出：-1
解释：无法将 x 减到 0。

示例 3：

输入：nums = [3,2,20,1,1,3], x = 10
输出：5
解释：最佳解决方案是移除前三个元素 [3,2,20] 和后两个元素 [1,3]，共计 5 次操作。

提示：

1 <= nums.length <= 105
1 <= nums[i] <= 104
1 <= x <= 109

解法（滑动窗口）：

算法思路：

题目要求找到移除的最少操作数，使得 x被减为0。实际上，这可以转换为在数组中找到和为 sum(nums) - x 的最长子数组，剩下的部分就是需要移除的最小操作数。
问题本质是找到和为 target = sum(nums) - x 的最长连续子数组，然后通过滑动窗口进行求解。

算法流程：

计算目标和：先计算数组的总和 sum，然后求出 target = sum - x。如果 target < 0，直接返回 -1。
滑动窗口初始化：使用两个指针 left 和 right 来控制窗口，并通过维护一个窗口的和 sum 来查找目标值。
滑动窗口操作：
- 扩展窗口时，右移 right 指针，增加窗口的和。
- 收缩窗口时，左移 left 指针，减小窗口的和。
- 当窗口和等于 target 时，更新最长子数组的长度。
返回结果：如果找到满足条件的最长子数组，返回 nums.size() - maxLen；否则返回 -1。

代码实现：

class Solution {
public:
    int minOperations(vector<int>& nums, int x) {
        // 1. 计算数组总和和目标和
        int sum = 0;
        for (int a : nums) sum += a;
        int target = sum - x;
        if (target < 0) return -1;

        // 2. 滑动窗口查找和为 target 的最长子数组
        int ret = -1;
        for (int left = 0, right = 0, tmp = 0; right < nums.size(); right++) {
            tmp += nums[right]; // 扩展窗口
            while (tmp > target) tmp -= nums[left++]; // 收缩窗口
            if (tmp == target) ret = max(ret, right - left + 1); // 更新最大长度
        }
        
        // 3. 返回结果：数组总长度减去最长子数组长度
        return ret == -1 ? -1 : nums.size() - ret;
    }
};

图解分析：

假设 nums = [1,1,4,2,3]，x = 5，即目标是找到和为 sum(nums) - x = 11 - 5 = 6 的最长子数组。

步骤图解：

Iteration	Left	Right	Window Sum	Subarray	Max Length (Result)
1	0	0	1	[1]	-1
2	0	1	2	[1, 1]	-1
3	0	2	6	[1, 1, 4]	3
4	0	3	8	[1, 1, 4, 2]	3
5	1	3	7	[1, 4, 2]	3
6	2	3	6	[4, 2]	3
7	2	4	9	[4, 2, 3]	3
8	3	4	5	[2, 3]	3

详细说明：

Iteration 1：Right=0，加入元素 1，窗口和为 1，还没达到目标和 6，最大长度保持 -1。
Iteration 2：Right=1，加入元素 1，窗口和为 2，还没达到目标和，最大长度保持 -1。
Iteration 3：Right=2，加入元素 4，窗口和为 6，正好达到了目标和 6，最大子数组长度更新为 3。
Iteration 4：Right=3，加入元素 2，窗口和为 8，超出目标和 6，开始移动 left 指针缩小窗口。
Iteration 5：Left=1，去掉左侧元素 1，窗口和为 7，仍然超出目标和，继续移动 left。
Iteration 6：Left=2，去掉左侧元素 1，窗口和为 6，再次达到了目标和，但最大子数组长度仍然为 3。
Iteration 7：Right=4，加入元素 3，窗口和为 9，超过目标和，继续移动 left。
Iteration 8：Left=3，去掉左侧元素 4，窗口和为 5，窗口不再满足条件，结束循环。

写在最后

在这篇文章中，我们详细介绍了滑动窗口这一高效的算法技巧，并通过四道经典题目逐步剖析了它的核心思想和实际应用。在长度最小的子数组、无重复字符的最长子串、最大连续 1 的个数 III 以及将 x 减到 0 的最小操作数等问题中，滑动窗口均展现了其强大的解决区间问题的能力。
通过这篇文章，读者不仅可以掌握滑动窗口的基础原理，还能够通过具体的题目理解如何灵活运用滑动窗口解决实际的算法问题。从优化时间复杂度到减少重复计算，滑动窗口无疑是处理连续区间问题的强力工具。希望大家在理解并掌握这些基础应用后，能够在更复杂的场景中灵活应用这一技巧。
我们将在下一篇文章中深入探讨滑动窗口的进阶应用，包括处理更复杂的数据结构、动态窗口调整等内容，进一步提升大家在算法优化中的实战能力。

以上就是关于【优选算法篇】双指针的华丽探戈：深入C++算法殿堂的优雅追寻的内容啦，各位大佬有什么问题欢迎在评论区指正，或者私信我也是可以的啦，您的支持是我创作的最大动力！❤️

本文参与腾讯云自媒体同步曝光计划，分享自作者个人站点/博客。

原始发表：2024-10-17，如有侵权请联系 cloudcommunity@tencent.com 删除

指针