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

LeetCode 1004：最大连续1的个数 III（滑动窗口） —— 题解

news 2026/8/14 15:41:59

👋 欢迎阅读

一.题目

1004. 最大连续1的个数 III - 力扣（LeetCode）

🎯 欢迎来到「最大连续1的个数 III」题解之旅！本文将带你从“翻转最多 k 个 0 来获得最长连续 1”这一实际场景出发，深入理解滑动窗口（双指针）的灵活运用，并掌握如何通过维护窗口内 0 的个数不超过 k来高效求解最大窗口长度。

在开始之前，建议你先：

了解题目背景：这是 LeetCode 1004 题，给定一个二进制数组nums和一个整数k，允许将最多 k 个 0 翻转成 1，求翻转后数组中连续 1 的最大个数。本质上，我们要找到一个最长的连续子数组，使得其中 0 的个数不超过 k，因为我们可以把这些 0 全部翻转为 1，从而得到一段全 1 的连续区间。
明确学习目标：掌握滑动窗口核心流程——右指针right不断向右扩展，每遇到一个 0 就增加窗口内 0 的计数；如果计数超过k，则移动左指针left缩小窗口，直到窗口内 0 的个数 ≤ k；在此过程中不断更新窗口长度的最大值。理解为什么这种“右扩左缩”的策略能遍历所有可能的窗口，并保证找到最优解，同时熟练处理边界情况（如k=0或全为 1）。
准备好环境：建议在本地 IDE 或 LeetCode 在线编辑器中打开代码，边看边运行，亲手验证示例（如nums = [1,1,1,0,0,0,1,1,1,0], k = 2输出6）。

本文将从问题转化、滑动窗口策略设计（0 计数约束）、窗口收缩条件到代码实现，层层递进。即使你对滑动窗口还不熟悉，我们也会从“维护一个最多包含 k 个 0 的窗口，并尝试拉长它”这一直觉出发，让你轻松抓住核心思想——窗口内 0 的数量是唯一限制条件，用双指针动态调整窗口，使窗口在满足条件时尽可能长。现在，让我们一起在二进制数组中滑动窗口，找出翻转后最长的连续 1 吧！ 🔢📏

二.做题思路

一、问题分析（前置分析）

给定一个二进制数组nums和一个整数k，最多可以将k个 0 翻转为 1，求翻转后最长的连续 1 的子数组长度。
核心观察：等价于寻找一个最长的子数组，使得其中 0 的个数不超过k。这符合滑动窗口的特性，因为窗口内 0 的个数随右指针扩展而增加，随左指针收缩而减少。

二、算法策略（滑动窗口）

使用左右指针left和right维护窗口，变量zero记录窗口内 0 的个数。
右指针right从 0 到 n-1 依次遍历，将nums[right]加入窗口，若为 0 则zero++。
若zero > k，则收缩左指针left++，同时若移出的是 0 则zero--，直到zero <= k。
每次调整后，更新最长窗口长度len = max(len, right - left + 1)。

示例执行过程（nums = [1, 1, 0, 0, 1, 1, 1, 0, 1, 1],k = 2）：

步骤	`right`	`nums[right]`	入窗后`zero`	`zero > k?`	操作（收缩）	当前窗口`[left, right]`	窗口长度	`len`更新
初始	-	-	0	-	-	-	-	0
1	0	1	0	否	-	[0,0]	1	1
2	1	1	0	否	-	[0,1]	2	2
3	2	0	1	否	-	[0,2]	3	3
4	3	0	2	否	-	[0,3]	4	4
5	4	1	2	否	-	[0,4]	5	5
6	5	1	2	否	-	[0,5]	6	6
7	6	1	2	否	-	[0,6]	7	7
8	7	0	3	是	左移：移除`nums[0]=1`，`zero`仍为3；继续移除`nums[1]=1`，仍为3；移除`nums[2]=0`，`zero--`变为2，`left=3`	[3,7]	5	7（保持）
9	8	1	2	否	-	[3,8]	6	7（保持）
10	9	1	2	否	-	[3,9]	7	7（保持）

最终len = 7，对应子数组[1, 1, 1, 0, 1, 1, 1]（通过翻转两个 0 为 1，实际上原窗口[3,9]包含两个 0，翻转后全为1，长度为7）。

三、正确性说明（简单版本）

滑动窗口始终维护包含最多k个 0 的连续子数组。当窗口内 0 的个数超过k时，必须移动左指针直到满足条件，因为继续扩展右指针不会减少 0 的个数。这种“不满足就收缩”的策略，保证了在右指针固定的情况下，当前窗口是以该右端点为结尾的最长有效子数组。遍历所有右端点，记录最大值，即可得到全局最优解。由于每个元素最多入窗出窗一次，算法正确且高效。

四、实现细节（边界防护）

初始化left = 0，right = 0，zero = 0，len = 0。
for (int right = 0; right < n; ++right)遍历：
- 若nums[right] == 0，zero++；
- while (zero > k)循环：若nums[left] == 0，zero--；left++；
- 更新len = max(len, right - left + 1)。
若n == 0直接返回 0（但题目保证 n ≥ 1）。
时间复杂度 O(n)，空间复杂度 O(1)。

五、返回值（目标映射）

返回len，即翻转后最长连续 1 的个数。

三.代码

#include <iostream> #include <vector> #include <algorithm> using namespace std; class Solution { public: int longestOnes(vector<int>& nums, int k) { // 算法思路：滑动窗口（双指针） // 维护一个窗口 [left, right]，使得窗口内 0 的个数不超过 k。 // 右指针不断向右扩展，每遇到一个 0 就增加 zero 计数； // 如果 zero 超过 k，则左指针右移，同时如果左指针移出的是 0，则 zero 减 1。 // 在每次调整后，更新窗口长度（right - left + 1），记录最大值。 int n = nums.size(); int zero = 0; // 当前窗口内 0 的个数 int len = 0; // 记录满足条件的最长窗口长度 // 双指针 left 和 right 定义窗口 [left, right] for (int left = 0, right = 0; right < n; right++) { // 入窗口：将 nums[right] 加入窗口 if (nums[right] == 0) { zero++; // 如果是 0，增加窗口内 0 的计数 } // 判断条件：如果窗口内 0 的个数超过 k，则需要收缩左边界 while (zero > k) { // 出窗口：将 nums[left] 移出窗口 if (nums[left] == 0) { zero--; // 如果移出的是 0，减少计数 } left++; // 左指针右移，缩小窗口 } // 更新结果：当前窗口满足条件（0 的个数 <= k），计算窗口长度 len = max(len, right - left + 1); } // 返回最长连续 1 的个数（即满足条件的最大窗口长度） return len; } }; int main() { // 测试用例：示例 1，期望输出 6 vector<int> nums = {1, 1, 1, 0, 0, 0, 1, 1, 1, 0}; int k = 2; Solution sol; int result = sol.longestOnes(nums, k); cout << result << endl; // 输出 6 return 0; }

四、易错点分析

难点一：`for`循环中`right`自增与窗口收缩的先后顺序

for (int left = 0, right = 0; right < n; right++) { if (nums[right] == 0) { zero++; } while (zero > k) { /* 收缩左边界 */ } len = max(len, right - left + 1); }

为什么容易困惑？
常规滑动窗口有时会在收缩后才更新len，但这里每次right扩展后立即入窗口，然后收缩，最后才更新长度。难点在于：len的更新是在while收缩之后，这意味着当前窗口始终是“合法”的（0 的个数 ≤ k），因此可以直接用right - left + 1。
初学者可能误以为应该在入窗口前或收缩前更新长度，而本代码利用“先入后缩”的顺序，保证了更新时窗口已合法，这是理解上的关键转折点。

难点二：`zero`计数与`left`移出元素的关联

while (zero > k) { if (nums[left] == 0) { zero--; } left++; }

核心难点：
zero只记录当前窗口内 0 的个数，但当left右移时，需要判断移出的元素是否为 0。这里容易混淆的是：left移动后，zero的减少仅发生在移出元素是 0 的情况下；如果移出的是 1，zero不变。
这个逻辑虽简单，但在调试时容易因为遗漏if判断而误以为left每动一次zero都要减 1，导致计数错误。理解“只减移出的 0”是掌握本算法的前提。

难点三：窗口长度的更新位置与最大值的维护

len = max(len, right - left + 1);

难点在于为什么放在这里？
因为经过while收缩后，窗口[left, right]一定满足zero ≤ k，此时窗口内所有 0 都可以通过翻转变成 1，所以当前窗口长度就是一个可行解。
初学者可能认为只需在right扩展时更新一次，但若left发生了移动，窗口长度会变化，必须每次收缩后重新计算才能保证不遗漏更优解。这个位置强调了“每次调整后都取最大”的思想。

五、流程图

🎯 闭幕

🎉 恭喜你完成了「最大连续1的个数 III」问题的学习！

为了巩固知识并进一步拓展，建议你：

🚀动手实践
在 LeetCode 上提交代码，尝试不同的测试用例。

💡深入思考

本题使用滑动窗口维护一个0 的个数不超过 k的区间，右指针不断扩展，当窗口内 0 的个数超过 k 时移动左指针。请问为什么当 zero > k 时，只需要移动一次左指针就可以继续？能否一次性跳到更远的位置？
代码中当nums[right] == 0时zero++，当nums[left] == 0时zero--。为什么只统计 0 的数量，而不需要统计 1 的数量？
如果k = 0，问题退化为求最长连续 1 子数组，当前算法是否仍然正确？请验证。
滑动窗口的时间复杂度为O(n)，因为每个元素最多被左右指针各访问一次。如果数组长度n = 10^5，这个算法是否高效？
本题要求最多翻转 k 个 0，相当于将窗口内的 0 视为“可以容忍的”。如果要求最多可以删除 k 个元素（不限定 0 或 1），使剩余部分中连续 1 最长，算法应如何调整？

📚延伸挑战

如果问题改为最多翻转 k 个 1（使连续 0 最长），代码只需改动哪一处即可？
如果数组中的数字不只是 0 和 1，而是包含多种取值（例如颜色分类中的 0,1,2），要求通过最多 k 次修改使得某种指定值连续最长，你会如何设计通用的滑动窗口框架？

如果你觉得本文对你有所帮助，欢迎：

👍点赞 / 收藏
👤关注作者，获取更多题解
💬留言交流你的疑问或优化思路

📌深入思考答案

只移动一次左指针即可，因为滑动窗口的特性是每次右指针移动一步，左指针也至多移动一步，保证窗口始终合法，且每个位置作为窗口起点最多被考虑一次，这是 O(n) 的基础。一次性跳到更远位置虽可行，但会增加代码复杂度，且不利于维护窗口连续性。
只需统计 0 的数量，因为窗口内 1 的数量 = 窗口长度 - 0 的数量，而翻转 0 后都变成 1，连续 1 的长度就是窗口长度，所以只要 0 的个数 ≤ k，窗口长度就是答案，无需额外统计 1。
k=0时，zero > 0 立即收缩左指针，窗口内始终保持 0 的个数为 0，即窗口内全为 1，算法退化为求最长连续 1 子数组，逻辑正确。
O(n) 对n=10^5非常高效，完全可接受。
若允许删除任意 k 个元素，问题变为求删除 k 个元素后最长连续 1 子数组，本质上仍然是容忍 k 个非 1 元素，只需将判断条件改为统计窗口内非 1 的个数即可，逻辑相同。

🔍延伸挑战答案

挑战1：只需将判断条件从nums[right] == 0改为nums[right] == 1，zero改为统计 1 的个数即可，其余逻辑不变，即可求最长连续 0 子数组。
挑战2：将统计条件改为目标值以外的元素计数，即bad++当nums[right] != target，收缩时判断bad > k，即可实现通用滑动窗口，适用于任意离散取值的数组。