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

1. ​题目链接

1004. 最大连续1的个数 III - 力扣（LeetCode）https://leetcode.cn/problems/max-consecutive-ones-iii/

---

2. ​题目描述

给定一个二进制数组 nums 和一个整数 k，允许将最多 k 个 0 翻转为 1，求翻转后最长的连续 1 的子数组长度。
示例：
输入：nums = [1,1,1,0,0,0,1,1,1,1,0], k = 2
输出：6（最长子数组为 [1,1,1,0,0,1,1,1,1]，翻转两个0后连续1的长度为6）

---

3. ​算法思路

采用滑动窗口（双指针）​算法：

1. ​窗口定义：维护 left 和 right 指针，表示当前窗口范围。
2. ​统计0的数量：窗口内允许的0的数量不超过 k。
3. ​窗口扩展：右指针 right 不断右移，遇到0时增加计数。
4. ​窗口收缩：当0的数量超过 k 时，左指针 left 右移，直到0的数量合法。

---

4. ​代码实现分析

class Solution
{
public:int longestOnes(vector<int>& nums, int k){int n = nums.size();if (k >= n) return n; // 边界条件int left = 0, right = 0;int zeroCount = 0, maxLen = 0, curLen = 0;// 进窗口for (right = 0; right < n ; right++){if (nums[right] == 0) zeroCount++;// 出窗口while (zeroCount > k){if (nums[left++] == 0) zeroCount--;}// 最长字串更新maxLen = max(right - left + 1, maxLen);}return maxLen;}
};

关键点解析：

1. ​边界处理：k >= n 时直接返回数组长度，因为可以翻转所有0。
2. ​滑动窗口逻辑：
   • ​右指针扩展：每次移动右指针并统计0的数量。
   • ​左指针收缩：当0的数量超过 k 时，左指针右移，直到窗口合法。
3. ​时间复杂度：O(n)，每个元素最多被访问两次（左、右指针各一次）。

---

4. ​总结

该代码通过滑动窗口算法高效解决了问题，逻辑清晰且时间复杂度最优。关键在于实时更新最大值和精确控制窗口收缩条件，避免遗漏可能的解。

对比维度	​暴力枚举法	​滑动窗口法
​核心思想	遍历所有可能的子数组，检查是否可以通过翻转最多 k 个 0 变成全 1 的子数组。	维护一个动态窗口，窗口内最多允许 k 个 0，通过调整左右指针高效寻找最长子数组。
​时间复杂度	O(n²)（双重循环枚举所有子数组起点和终点，每个子数组统计0的时间为 O(1)*）。	O(n)（每个元素仅被左右指针访问一次，总操作次数为 2n）。
​空间复杂度	O(1)（无需额外存储结构）。	O(1)（仅需常数变量记录0的数量和指针位置）。
​实现方式	1. 双重循环枚举所有子数组起点 i 和终点 j。 2. 对每个子数组 [i, j]，统计其中 0 的数量是否 ≤ k。	1. 右指针 right 不断右移，统计窗口内 0 的数量。 2. 若 0 的数量超过 k，左指针 left 右移直到合法。 3. 实时更新最大窗口长度。
​适用场景	数据规模极小（如 n ≤ 100）。	数据规模大（如 n ≥ 1e4），需高效处理连续子数组问题。
​优点	实现简单，逻辑直观，适合验证算法正确性。	时间复杂度最优，避免冗余计算，适用于高频或大规模数据场景。
​缺点	数据规模大时性能极差（例如 n=1e4 时需 1e8 次操作）。	需合理控制窗口收缩逻辑，对边界条件处理要求较高（如 k=0 或全为 0 的数组）。