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

1. ​ 题目链接

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

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

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. ​ 总结

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