C++算法
C++ 滑动窗口算法详解：基础题解与思维分析
通过 C++ 代码详细讲解了滑动窗口算法，涵盖长度最小的子数组、无重复字符的最长子串、最大连续 1 的个数 III 及将 x 减到 0 的最小操作数四道经典题目。分析了暴力解法与滑动窗口的区别，阐述了双指针移动原理及时间复杂度优化过程，帮助读者掌握处理连续区间问题的核心技巧。
通过 C++ 代码详细讲解了滑动窗口算法，涵盖长度最小的子数组、无重复字符的最长子串、最大连续 1 的个数 III 及将 x 减到 0 的最小操作数四道经典题目。分析了暴力解法与滑动窗口的区别，阐述了双指针移动原理及时间复杂度优化过程，帮助读者掌握处理连续区间问题的核心技巧。
滑动窗口是一种常用的算法技巧，主要用于处理子数组、子串等具有'窗口'特性的题目。在本篇博客中，我们将通过具体的例题讲解，深入剖析滑动窗口的思想和它的应用场景。滑动窗口法能够在保持高效计算的同时，减少重复的工作，因而在处理某些连续区间问题时，常常是最优解法。
题目链接：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 |
图解说明：
left = 0，右端扩展到 right = 3，子数组 [2, 3, 1, 2] 的和为 8，大于 target，记录最小长度为 4。left 右移到 1，新窗口和为 6，小于 target，不更新结果。4，子数组和为 10，更新最小长度为 4。left 右移到 2，子数组 [1, 2, 4] 的和为 7，更新最小长度为 3。left 再次右移，和降到 6，小于 target，不更新结果。right 扩展到 5，子数组 [2, 4, 3] 的和为 9，不更新最小长度。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 时，我们才能缩小窗口。题目链接：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^4s 由英文字母、数字、符号和空格组成算法思路： 通过枚举从每个位置开始，向后寻找无重复字符的子串能到达的位置，记录其中最长的子串长度即可。在寻找无重复子串时，可以使用哈希表统计字符出现的频次，遇到重复字符时停止。
具体步骤：
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 |
Left=0，Right=0，加入字符 a，哈希表为 a:1，当前子串为 "a"，长度为 1。Right=1，加入字符 b，哈希表为 a:1, b:1，当前子串为 "ab"，长度为 2。Right=2，加入字符 c，哈希表为 a:1, b:1, c:1，当前子串为 "abc"，长度为 3。Right=3，加入字符 a，哈希表更新为 a:2, b:1, c:1。由于字符 a 出现两次，移动 Left 指针到 1，此时子串变为 "bca"，长度仍然是 3。Right=4，加入字符 b，哈希表更新为 b:2, c:1, a:1。由于字符 b 出现两次，移动 Left 到 2，子串变为 "cab"，长度保持为 3。Right=5，加入字符 c，哈希表更新为 b:1, c:2, a:1。此时字符 c 出现两次，需要再次移动 Left，将 Left 移到 3，此时子串变为 "abc"，长度为 3。Right=6，加入字符 b，哈希表更新为 b:2, c:1。由于 b 出现两次，移动 Left 到 left=5，此时子串应为 "cb"，长度为 2。Right=7，继续加入字符 b，哈希表更新为 b:2，再次出现重复字符，移动 Left 到 6，子串为 "b"，长度为 2。题目链接：1004. 最大连续 1 的个数 III
题目描述：
给定一个二进制数组 nums 和一个整数 k，如果可以翻转最多 k 个 0，则返回数组中 连续 1 的最大个数。
示例 1：
nums = [1,1,1,0,0,0,1,1,1,1,0], K = 260 变为 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 = 3100 变为 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 |
Right=0 到 Right=2，我们持续遇到 1，所以窗口扩展，Zero Count 仍为 0，子数组 [1,1,1] 长度逐渐增加到 3。Right=3，遇到一个 0，Zero Count=1，但还在 k=2 的允许范围内，子数组 [1,1,1,0] 长度为 4。Right=4，再遇到一个 0，Zero Count=2，此时子数组 [1,1,1,0,0] 满足条件，长度增加到 5。Right=5，再遇到一个 0，Zero Count=3，超出 k=2 的限制。因此需要缩小窗口，Left 开始向右移动。最终 Left 移动到 4，窗口变为 [0, 0]，Zero Count 恢复到 2，子数组长度保持为 5。Right 不断扩展，子数组逐渐变为 [0,0,1,1,1]，虽然 Zero Count 始终为 2，但最大长度仍为 5。Right=9，加入一个 1，窗口变为 [0,0,1,1,1,1]，满足 Zero Count=2，子数组长度增加到 6。Right=10，遇到一个 0，Zero Count=3，再次超过限制，因此移动 Left，直到 Left=5，窗口变为 [0, 1, 1, 1, 1, 0]，最大长度仍为 6。每次当 0 的数量超过 k 时，我们通过移动 left 指针来缩小窗口，直到窗口内的 0 的数量不超过 k。当窗口合法时，不断更新最长子数组的长度。
题目描述：
给你一个整数数组 nums 和一个整数 x。每次操作时，你可以移除数组 nums 的最左边或最右边的元素，然后从 x 中减去该元素的值。请注意，你需要修改数组以供接下来的操作使用。如果可以将 x 恰好减到 0，返回最少的操作数；否则，返回 -1。
示例 1：
nums = [1,1,4,2,3], x = 5[2,3]，将 x 减为 0。示例 2：
nums = [5,6,7,8,9], x = 4-1x 减到 0。示例 3：
nums = [3,2,20,1,1,3], x = 105[3,2,20] 和后两个元素 [1,3]，共计 5 次操作。提示：
1 <= nums.length <= 10^51 <= nums[i] <= 10^41 <= x <= 10^9算法思路：
题目要求找到移除的最少操作数，使得 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 |
Right=0，加入元素 1，窗口和为 1，还没达到目标和 6，最大长度保持 -1。Right=1，加入元素 1，窗口和为 2，还没达到目标和，最大长度保持 -1。Right=2，加入元素 4，窗口和为 6，正好达到了目标和 6，最大子数组长度更新为 3。Right=3，加入元素 2，窗口和为 8，超出目标和 6，开始移动 left 指针缩小窗口。Left=1，去掉左侧元素 1，窗口和为 7，仍然超出目标和，继续移动 left。Left=2，去掉左侧元素 1，窗口和为 6，再次达到了目标和，但最大子数组长度仍然为 3。Right=4，加入元素 3，窗口和为 9，超过目标和，继续移动 left。Left=3，去掉左侧元素 4，窗口和为 5，窗口不再满足条件，结束循环。本文详细介绍了滑动窗口这一高效的算法技巧，并通过四道经典题目逐步剖析了它的核心思想和实际应用。在长度最小的子数组、无重复字符的最长子串、最大连续 1 的个数 III 以及将 x 减到 0 的最小操作数等问题中，滑动窗口均展现了其强大的解决区间问题的能力。
通过这篇文章，读者不仅可以掌握滑动窗口的基础原理，还能够通过具体的题目理解如何灵活运用滑动窗口解决实际的算法问题。从优化时间复杂度到减少重复计算，滑动窗口无疑是处理连续区间问题的强力工具。
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online