LeetCode 1004：滑动窗口与双指针巧解最大连续1的个数

1. 题目解读与核心思路先说结论LeetCode 1004. Max Consecutive Ones III最大连续1的个数 III是一道非常经典的滑动窗口题目也是面试中高频出现的“变种双指针”问题。题目本身不复杂但很多人在第一次做的时候会栽在“翻转”这个描述上——误以为要真的去修改数组里的0结果把自己绕进去了。题目原文大致意思是给定一个二进制数组nums只包含0和1和一个整数k你最多可以把k个0变成1求变换后数组中连续1的最大长度。举个直观的例子nums [1,1,0,0,1,1,1,0,0,0],k 2。你最多把2个0改成1最长连续1的区间是[1,1,0,0,1,1,1]这个范围把中间两个0改掉长度为7。注意这里不能跨过三个连续的0因为k只有2。这道题适合三类人刚学完滑动窗口想找一道经典题目练手的初学者准备面试需要快速复习“最长子数组”类问题的求职者想深入理解双指针思想搞懂窗口收缩逻辑的刷题人我当年第一次做这题的时候第一反应是“贪心模拟翻转”结果写了一堆if-else边界条件处理得稀烂最后超时。后来老老实实按滑动窗口重新写十分钟就搞定了。所以这篇博文重点讲清楚两个东西为什么不能用“真翻转”的思路以及滑动窗口的窗口收缩条件到底怎么定。2. 滑动窗口的思考路径与原理拆解2.1 为什么“真正翻转”是死路很多人拿到题会想既然最多可以把k个0变成1那我是不是先找到所有0的位置然后枚举翻转哪k个再看最长连续1这个思路在k很小、数组很短的时候勉强能跑但一旦n到了10^5级别枚举组合就是指数级复杂度直接爆炸。换个角度想题目要的是“最长连续1的长度”并不关心最终数组长什么样。我们只需要在某个区间内0的个数不超过k那么这个区间里的所有0都可以被翻转成1区间长度就是潜在的答案。这样一来问题就变成了找一个最长的子数组使得其中0的个数不超过k。至于具体翻哪几个0根本不重要。这个转化非常关键它把“修改数组”变成了“统计区间内0的个数”。统计0的个数用前缀和或者滑动窗口都行但滑动窗口显然是更省空间、更好写的方案。2.2 窗口伸缩的核心逻辑滑动窗口的精髓是右指针不断向右扩展把新元素纳入窗口一旦窗口内0的个数超过k左指针就向右移动直到0的个数回到k以内。整个过程只需要一趟遍历时间复杂度O(n)空间复杂度O(1)。为什么这样是正确因为我们要找的是全局最长区间右指针每到达一个新位置窗口就对应一个“以该位置为右端点”的最长合法区间。当0的数量超限时左指针收缩把多余的0“挤出去”剩下的窗口一定是以当前右端点为终点的合法最长窗口。把所有右端点对应的窗口长度取最大值就是答案。这里有一个容易混淆的点左指针收缩后窗口长度不一定是严格单调的但右指针每步都向右移动所以每个右端点至少被考虑一次。你不需要把窗口收缩到“最优”再移动右指针只需要保证窗口合法即可因为最终答案一定会在某个右端点处被记录下来。3. C语言实现与代码逐段解析3.1 直接可跑的C代码先给出完整代码用C99标准即可不需要额外依赖。int longestOnes(int* nums, int numsSize, int k) { int left 0, right 0; int zeros 0; // 当前窗口内0的个数 int maxLen 0; while (right numsSize) { // 右指针纳入新元素 if (nums[right] 0) { zeros; } // 如果窗口内0的个数超过k收缩左边界 while (zeros k) { if (nums[left] 0) { zeros--; } left; } // 当前窗口[left, right]是合法的更新答案 int curLen right - left 1; if (curLen maxLen) { maxLen curLen; } right; } return maxLen; }3.2 逐行说明left和right是窗口的左右边界初始都在0。zeros记录窗口内0的数量这是判断窗口是否合法的核心变量。每次循环right先移动把nums[right]纳入窗口如果是0则zeros。内层while循环负责收缩左边界。只要zeros k说明当前窗口不合法需要把nums[left]移出窗口如果是0则zeros--然后left。注意这里用while而不是if因为可能连续移出多个元素才能让zeros降到k以下。收缩完成后窗口一定合法此时计算窗口长度right - left 1更新maxLen。然后right继续下一轮。这段代码最核心的细节是zeros的增减只跟0有关1完全不参与计数。所以1的数量不会影响窗口合法性只影响窗口长度。这听起来简单但很多人写着写着就把1也加进变量里导致收缩逻辑错误。3.3 为什么用while收缩而不是if以nums [0,0,0,1],k 1为例手动跑一遍right 0窗口[0,0]zeros1合法长度1。right 1窗口[0,1]zeros2不合法。此时需要收缩nums[left]也就是nums[0]是0zeros变1left变1。窗口[1,1]zeros1合法长度1。如果这里用的是if只收缩一次left会停在1zeros还是2吗不因为收缩了一次后zeros已经变1了所以if其实也能处理这个case。但换个例子nums [0,0,0,1],k 1当right 2时窗口[0,2]zeros3不合法。while循环会连续收缩第一次收缩nums[0]zeros2left1仍大于k第二次收缩nums[1]zeros1left2才停止。如果只收缩一次窗口[1,2]里两个0zeros2仍不合法答案就会出错。所以while是必须的if只能处理恰好超一个0的边界情况无法应对多个连续0造成的超额。4. 常见误区与边界情况排查4.1 误区一把窗口长度算成right - left而不是right - left 1这是新手最容易犯的错。因为很多滑动窗口题目里窗口长度是right - left比如求最短覆盖子串时用的是区间内元素个数但这里我们要的是闭区间长度必须加1。比如left 0, right 0窗口里只有一个元素长度显然是1right - left 1 1。4.2 误区二忘了处理k 0的情况当k 0时问题退化为找最长连续1的长度。上述代码天然适应因为zeros 0时就会收缩窗口内不允许有0。比如nums [1,0,1,1],k 0运行过程right0窗口[0,0]zeros0长度1。right1窗口[0,1]zeros1 0收缩nums[0]1zeros不变left1窗口[1,1]仍有一个0继续收缩nums[1]0zeros0left2窗口[2,1]这里注意left超过right了但没关系窗口为空长度0。然后right2窗口[2,2]是1长度1。最终答案是2索引2和3的两个1。可以看到left可以暂时超过right这是允许的因为后续right推进会重新建立合法窗口。你不需要额外保护left right的情况只要zeros是正确的窗口逻辑就不会崩。4.3 误区三用if代替while收缩上面已经详细解释过这里再强调一下当窗口里有连续多个0时必须一次收缩到合法为止。否则窗口内zeros会残留超额后续更新长度时得到的可能是非法窗口长度。4.4 边界情况速查表场景输入k预期输出说明全0数组[0,0,0]22最多把两个0变1最长是2全1数组[1,1,1]03不需要翻转最长是3空数组[]00数组为空返回0k大于0总数[0,0,1]53可以把所有0翻掉整个数组都是1交替数组[1,0,1,0,1]13最长是[1,0,1]或[1,0,1]长度为3单个元素[0]11一个0翻成1长度为14.5 关于C语言实现的几个小细节函数签名int longestOnes(int* nums, int numsSize, int k)是LeetCode默认提供的不用自己处理输入输出只需要返回答案即可。numsSize传入的是数组长度如果为0循环直接跳过最后返回0符合预期。变量类型方面int足够用因为数组长度和答案都在int范围内题目约束1 nums.length 10^5。5. 复杂度分析与同类题目扩展5.1 时间复杂度O(n)是这么来的外层while每个元素作为右端点进入窗口一次内层while每个元素最多作为左端点被移出窗口一次。左右指针都不回头所以整体操作次数不超过2n。虽然内层嵌套但均摊下来每个元素最多被处理两次时间复杂度是严格的O(n)。空间复杂度O(1)只用了几个整型变量这在面试中是很大的加分项因为很多同类题需要用哈希表辅助这里完全不需要。5.2 这题和“最长无重复子串”的关系如果做过LeetCode 3无重复字符的最长子串会发现二者框架几乎一样右指针扩展不符合条件时左指针收缩窗口内用某个计数器维护约束。区别在于无重复子串的约束是“字符不重复”这里的约束是“0的个数不超过k”。理解了这道题再去看LeetCode 3、LeetCode 424替换后的最长重复字符、LeetCode 487最大连续1的个数II其实和这题几乎一样都会豁然开朗。5.3 能不能用二分前缀和做能。如果你对滑动窗口不熟也可以用“前缀和数组记录0的个数”然后二分搜索答案长度len每次检查是否存在长度为len的区间其0个数不超过k。这个做法的复杂度是O(n log n)也可以通过但代码更长、常数更大。面试时如果能写出滑动窗口会更受青睐因为时间最优、思路更直接。5.4 一个脑洞如果把k变成“最多翻转1个”会怎样这道题的“III”暗示有前两题。LeetCode 485是找最长连续1不允许翻转LeetCode 487是允许翻转1个0即k1的特例1004是泛化版本。所以如果你已经刷过487那1004就是改一个参数的事。如果没刷过直接做1004也完全没问题。6. 实战经验与调试技巧6.1 自己写代码时的一个小习惯写滑动窗口题时我习惯在纸上先画出窗口的左右指针移动过程尤其是zeros这个计数器跟着变化的过程。画三步就够了比如拿[1,0,0,1,0,1],k2手算一遍确认每一步窗口合法。画完再写代码基本一次过。6.2 如果提交WA优先检查哪里先检查zeros增减是否只在nums[right]或nums[left]为0时发生。再检查收缩是while不是if。然后检查长度是否加1。最后检查maxLen是否在每次右指针移动后更新而不是在收缩后更新。这四步能解决90%的WA情况。我见过很多人把maxLen max(maxLen, right - left 1)放在收缩之后还错误地认为收缩后的窗口是最长的其实收缩后窗口反而变短了应该放在收缩前或者收缩后都行因为收缩后的窗口也是合法的但可能更短不影响最大值放在收缩后也不会错但放在收缩前更能体现“以当前右端点为终点的最长窗口”这个含义。6.3 一个容易忽略的细节如果nums里全是1那么zeros始终为0while循环一次都不会进入maxLen会一路增长到numsSize结果正确。如果nums里全是0zeros增长很快收缩也会很频繁但算法依然线性完成。你不需要单独处理“全是0”或者“全是1”的情况滑动窗口的自适应性很强。6.4 对比用for循环写会不会更好我个人觉得while更清晰因为左右指针都需要移动。如果用for (right 0; right numsSize; right)那left的移动就得放在内层while里代码也完全等价。看个人习惯但对于初学者while的对称性更好理解。7. 从这题延伸出的刷题建议7.1 同类题目练习路径如果你刚做完这题建议按顺序刷以下题目巩固滑动窗口的变种LeetCode 3无重复字符的最长子串哈希表窗口收缩条件不同LeetCode 424替换后的最长重复字符额外维护窗口内出现最多的字符LeetCode 487会员题最大连续1的个数II本题的k1特例LeetCode 209长度最小的子数组窗口收缩条件变为和targetLeetCode 76最小覆盖子串窗口收缩条件变为覆盖所有目标字符刷完这几道你对“滑动窗口三要素”——窗口扩展、窗口收缩、答案更新——会有肌肉记忆。这三要素几乎能套用80%的子数组/子串问题。7.2 面试时如何讲解如果面试官让你解释这题建议按这个顺序说把“翻转0”转化为“窗口内允许有k个0”。用双指针维护窗口右指针负责扩展左指针负责收缩。保证窗口内0的个数不超过k。实时记录窗口最大长度。说清楚这四点面试官就会觉得你思路清晰甚至会追问你“能不能优化到O(n)”你直接把代码写出来即可。7.3 一个进一步的思考如果把数组元素从0/1扩展为任意整数把“0的个数不超过k”改为“不同数字的个数不超过k”那这题就变成了LeetCode 340至多包含K个不同字符的最长子串。你会发现代码几乎只需要改计数器从zeros换成distinctCount再加上一个哈希表。这就是滑动窗口的通用性——你掌握的是框架不是某一道题的模板。8. 最后的实操心得我在本地用C语言调试时习惯写一个简单的main函数来测试而不是直接提交到LeetCode。一个典型的测试框架大概长这样#include stdio.h int longestOnes(int* nums, int numsSize, int k); int main() { int nums1[] {1,1,1,0,0,0,1,1,1,1,0}; printf(%d\n, longestOnes(nums1, 11, 2)); // 期望6 int nums2[] {0,0,1,1,1,0,0,0,1,1,0,0,1}; printf(%d\n, longestOnes(nums2, 13, 3)); // 期望7 int nums3[] {0,0,0,0}; printf(%d\n, longestOnes(nums3, 4, 0)); // 期望0 return 0; }这样测试的好处是你可以用几个自己心算过的例子快速验证逻辑而不是直接依赖LeetCode的报错反馈。LeetCode的判题结果只有“通过/不通过”看不到具体的中间变量本地调试能看到每一步的窗口状态。如果你是在VSCode里配置了C/C环境直接用调试器设置断点在updated maxLen那一行观察left、right、zeros的变化会非常直观。我第一次就把断点设在收缩while内部然后把数组换成[0,1,0,0,1,0],k2单步跑了三圈瞬间明白为什么收缩要一直循环。这题整体难度不高但却是检验你是否真正理解滑动窗口的试金石。能独立写出正确代码的人通常也能把窗口收缩条件解释清楚。反之如果连这题都要纠结半天那建议先把双指针基础补一补。我个人经验是把这题吃透后再刷同类题时几乎不需要再翻别人的题解了。