LeetCode 1004 这道 Max Consecutive Ones III是我刷滑动窗口专题时印象最深的一道题。它表面上是“数连续 1 有多长”但加了一个 k 的翻转配额之后整个问题的复杂度立刻不一样了。我第一次写的时候脑子里只有“枚举所有子数组”这个笨办法数据量稍微大一点就超时。后来才真正搞明白这题的标准解法是滑动窗口加双指针用 C 语言写出来也就二十行出头但里面藏着一个很关键的细节为什么窗口不合法时只平移一格就够了这地方卡住过不少人。如果你正在刷 LeetCode 热门 100 题或者刚进入滑动窗口这个专题这道题是一个非常典型的“入门到进阶”样本。它不涉及什么高深的数据结构但能把双指针的单调性、窗口收缩的时机、边界条件的处理一次讲全。这篇文章我会从暴力思路开始推把为什么必须用滑动窗口、C 语言实现怎么写、两版代码有什么区别、常见的坑有哪些全部展开讲透。用到的示例数组就是题目自带的官方样例方便你对照跑。1. 先看懂题它到底在问什么1.1 翻转 0 只是障眼法本质是“容忍 k 个 0”原题给的是一个二进制数组也就是数组里只有 0 和 1。你可以把最多 k 个 0 变成 1问变换之后最长的连续 1 子数组有多长。题目名称叫 Max Consecutive Ones III前面还有 I 和 III 是 k0 的特殊情况II 是 k1 的特殊情况III 才是完整的通用版本。我第一次读题时很容易被“翻转”这个动作带偏以为要真的找哪几个 0 值得翻。但仔细想一下翻转 0 的目的是让一段区间内的元素全部变成 1。也就是说我只需要关心某一段连续区间里 0 的个数是否不超过 k。只要不超过 k我就能把这 k 个 0 全部翻成 1这段区间就全是 1 了。至于具体翻哪几个根本不重要。所以题目的本质就变成了在一个 0/1 数组里找最长的连续子数组使得这个子数组里 0 的个数不超过 k。用生活里的话说就像你在查一条队伍里最长的一段“基本全勤”允许每 100 个人里有 k 个人请假只要缺勤人数不超标这段就算合格。1.2 暴力解和它的天花板先说最直接的暴力。枚举所有可能的子数组左端点和右端点对每个子数组统计 0 的个数如果不超过 k就更新答案。这个做法的时间复杂度是 O(n²) 的枚举乘以 O(n) 的统计整体是 O(n³)。如果提前用前缀和预处理可以在 O(1) 时间内拿到任意区间里 0 的个数整体降到 O(n²)。为什么 O(n²) 仍然不行因为题目给的数组长度上限是 10 的 5 次方级别。10 的 5 次方求平方是 10 的 10 次方这个量级在普通个人电脑上跑基本上是几十秒到几分钟的级别在 LeetCode 的判题环境下必然会超时。更别说 O(n³) 了那是 10 的 15 次方连现代超算都觉得吃力。从暴力到 O(n)缺的是一个观察随着右端点向右移动区间里 0 的个数不会减少只会增加或保持不变随着左端点向右移动区间里 0 的个数不会增加只会减少或保持不变。这个“单调性”是后面所有优化思路的地基。1.3 从暴力到双指针的那个关键观察因为 0 的个数随着区间右端点右移而单调不降随着区间左端点右移而单调不增所以存在一个性质如果某个区间 [l, r] 是合法的也就是 0 的个数不超过 k那么它的任意子区间也都是合法的。反过来如果 [l, r] 不合法那么把右端点继续向右扩只会更不合法。这个性质直接给了一个优化方向固定右端点 r让左端点 l 尽量小这样区间最长。当区间不合法时把 l 向右移动把多余的 0 移出去直到区间重新合法。因为 l 永远不需要回退r 一直向前整个过程每个位置最多被访问两次一次作为右端点被加入一次作为左端点被移出复杂度就是 O(n)。这就是滑动窗口。它在逻辑上很像一条传送带右端点负责“进货”左端点负责“质检”不合格就扔掉最左边的东西直到整条带子重新合格。2. 滑动窗口为什么是对的两种写法一次讲透2.1 窗口合法性的单调性写代码之前先把“为什么滑动窗口不会漏掉最优解”这个底层逻辑讲清楚。假设现在右指针固定在一个位置 r。在所有的合法窗口里以 r 为右端点、以当前 left 为左端点的窗口是目前能让 left 停下的最左位置。为什么因为 left 每向右移动一位窗口长度就减一在 left 停下来之前窗口一直是“0 的个数超过 k”的状态所以更短的窗口也不合法。只有当 left 移动到让 0 的个数回到 k 以内窗口才恢复合法。所以对每个右端点 r算法求出的窗口 [left, r] 是所有以 r 结尾的合法窗口中长度最大的那个。全局最优解一定以某个位置为右端点而我们遍历了所有右端点每个右端点都求出了该右端点的最长合法窗口那答案当然不会漏。这是“显式记录答案”版本的正确性逻辑。后面要讲的精简版本逻辑稍微绕一点但底层依赖的也是同一个单调性。2.2 显式记录答案的标准写法这个版本是最容易理解、也最推荐新手使用的写法。它的流程清清楚楚右指针一步步往前走每走一步就把新元素纳入窗口状态然后检查窗口是否合法。如果不合法就循环移动左指针直到重新合法。窗口合法之后用 right - left 1 更新答案。int longestOnes(int* nums, int numsSize, int k) { int left 0; int maxLen 0; int zeroCnt 0; for (int right 0; right numsSize; right) { if (nums[right] 0) { zeroCnt; } while (zeroCnt k) { if (nums[left] 0) { --zeroCnt; } left; } int len right - left 1; if (len maxLen) { maxLen len; } } return maxLen; }这里有两处细节容易写错。第一while 循环里判断 nums[left] 是否为 0只有在它确实是 0 的时候才把 zeroCnt 减一。如果把判断写成无条件减一那当 left 指向 1 时zeroCnt 会被错误地减掉导致后面窗口一直误判为合法答案会偏大。第二答案一定要在 while 收缩结束之后更新不能在刚加入 nums[right] 还没收缩之前更新否则可能把不合法窗口的长度也算进去。2.3 省掉答案变量的精简写法LeetCode 评论区里更常见的是下面这个精简版本它没有显式的 maxLen 变量最后直接返回 numsSize - left。很多第一次看到的人会困惑为什么只用一个 if 而不是 while为什么窗口都“不合法”了还能直接拿长度当答案int longestOnes(int* nums, int numsSize, int k) { int left 0; int zeroCnt 0; for (int right 0; right numsSize; right) { if (nums[right] 0) { zeroCnt; } if (zeroCnt k) { if (nums[left] 0) { --zeroCnt; } left; } } return numsSize - left; }核心逻辑是当窗口不合法时只把 left 向右移动一位right 继续向后走窗口长度保持原来的大小。这相当于整条窗口在“平移”而不是“收缩”。因为这道题求的是最大长度左指针收缩到让窗口变短的唯一结果就是得到一个更小的候选值而这个更小的值永远不会成为答案所以没必要收缩到完全合法。窗口长度在整个过程中只增不减每次长度增加的那一刻窗口必然是合法的。因此遍历到末尾时numsSize - left 就是算法维护过的最大合法窗口长度。我对这个版本的看法是代码确实漂亮但理解成本高。如果你只是刷题第一版足够如果你想把这段代码写进自己的模板库并在面试时默写我建议还是用第一版逻辑不容易出错。精简版适合在理解透彻之后用来给别人展示滑动窗口的“平移”思想。3. C 语言实现从函数签名到完整可跑代码3.1 LeetCode 的 C 语言接口和本地测试框架LeetCode 上 C 语言题的函数签名通常长这样int longestOnes(int* nums, int numsSize, int k)。这里的 nums 是数组首地址numsSize 是数组元素个数k 是最多允许翻转的 0 的数量返回值是 int。我在本地调试时会自己补一个 main 函数把官方示例作为测试数据跑一遍。很多人用 VSCode 配 C/C 环境调试这里提醒一句LeetCode 的评测环境已经帮你包含了很多头文件但本地跑需要自己加 #include stdio.h否则 printf 会报隐式声明警告。如果编译报错先检查是不是缺了头文件。3.2 标准写法的完整代码与逐行注释下面是我在本地完整跑通过的代码包含两个官方示例的测试。第二个示例的预期输出是 10正好对应官方题面里的第二个用例。#include stdio.h int longestOnes(int* nums, int numsSize, int k) { int left 0; int zeroCnt 0; int maxLen 0; for (int right 0; right numsSize; right) { // 1. 新元素进入窗口如果是 0 就累加 if (nums[right] 0) { zeroCnt; } // 2. 窗口不合法时左指针右移直到窗口重新合法 while (zeroCnt k) { if (nums[left] 0) { --zeroCnt; } left; } // 3. 此时窗口合法统计长度 int len right - left 1; if (len maxLen) { maxLen len; } } return maxLen; } int main(void) { 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, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1}; printf(%d\n, longestOnes(nums2, 19, 3)); // 期望 10 return 0; }这段代码里的 three 步结构是滑动窗口的通用骨架纳入窗口、处理不合法状态、更新答案。后面讲模板时会再用到。如果你把 numsSize 传成 0循环体一次都不执行maxLen 保持 0返回结果也正确所以不需要单独写空数组分支。3.3 复杂度分析与空间优化时间复杂度是 O(n)。这里 n 就是 numsSize。left 和 right 两个指针都只向一个方向移动right 最多移动 n 次left 在整个过程中也最多移动 n 次因为 left 不可能超过 right。所以总操作量是 2n 级别的常数倍标准写法下就是 O(n)。空间复杂度是 O(1)因为只用了 left、zeroCnt、maxLen 这几个固定数量的变量没有额外分配数组。这也是这道题作为经典题的原因之一思路直观实现简洁复杂度又是最优。对比一下二分加前缀和的 O(n log n) 解法滑动窗口在时间上更优代码量还更短所以面试里最优解基本就是滑动窗口。4. 手动推演一个样例看窗口怎么滑4.1 逐轮模拟第一版滑动窗口用官方示例一nums [1,1,1,0,0,0,1,1,1,1,0]k 2。我按第一版代码的逻辑把每一轮的核心状态列成一张表。这里 zeroCnt 表示当前窗口里的 0 的个数left 是窗口左边界maxLen 是到目前为止发现的最长合法窗口长度。rightnums[right]zeroCnt收缩后的 left窗口内容窗口长度maxLen0100[1]111100[1,1]222100[1,1,1]333010[1,1,1,0]444020[1,1,1,0,0]555034[0,0]256124[0,0,1]357124[0,0,1,1]458124[0,0,1,1,1]559124[0,0,1,1,1,1]6610035[0,1,1,1,1,0]66最值得看的是 right 5 那一轮。窗口 [0,5] 里 0 的个数是 3超过 k2while 循环开始收缩 left。left 从 0 往右走前三个位置 [0,1,2] 都是 1zeroCnt 不变真正让 zeroCnt 从 3 降到 2 的是 left 走到 3 时发现 nums[3] 0。这里展示了一个特别容易踩的坑left 移动过程中可能经过很多个 1它们和 0 的个数无关代码里必须写成 if (nums[left] 0) --zeroCnt而不是无脑减。4.2 窗口平移时刻为什么收缩可以“懒”继续看 right 10 那一轮。加入最后一个 0 之后zeroCnt 变成 3又要收缩。这一轮 left 从 4 走到 5因为 nums[4] 是 0zeroCnt 减到 2窗口变成 [5,10]长度还是 6。注意这里窗口平移之后内部依然是合法的因为它恰好把一个 0 移了出去。但如果是精简版写法收缩只执行一次。假设 nums[left] 恰好是 1那么 zeroCnt 没有变化窗口仍然不合法。这看起来好像违反了“窗口合法”的前提但没有关系因为窗口长度没有变小它只是在向右平移。最终窗口长度维持在一个历史上已经出现过合法状态的值上所以返回 numsSize - left 依然正确。这就是“懒收缩”的妙处求最大长度的窗口题目里收缩到恰好合法的操作是浪费的只要保证长度不缩水就够了。4.3 边界用例速查表写代码不仅要跑官方样例还要主动构造边界用例。我给出一组自己在本地测过的用例覆盖了最容易出错的几种情况。输入k期望输出说明[1,1,1,1]24全是 1不需要翻转结果是数组长度[0,0,0,0]00全是 0 且不允许翻转结果只能是 0[0,0,0,0]22全是 0最多翻转 k 个结果就是 k[0]11单个 0但配额充足可以翻成 1[1]01单个 1不需要翻转[1,0,1,0,1]13交替出现最优是翻转一个 0 得到长度 3[]00空数组循环不执行返回 0全 0 数组那个 case 特别值得注意。当 k 小于数组长度时答案就是 k当 k 不小于数组长度时整个数组全能变 1答案就是数组长度。5. 踩坑记录常见错误与排查思路5.1 三个最容易写错的点第一个 bug 是收缩窗口时忘记判断当前 left 指向的是不是 0。这个前面已经讲过了症状是 zeroCnt 被减成负数窗口一直被认为是合法的最终结果会比正确答案大。排查方法是打印每一轮的 zeroCnt如果发现它出现了负数基本就是这个原因。第二个 bug 是精简版里最后返回 right - left 1。这个写法在循环结束时会多算 1因为循环退出后 right 已经是 numsSize 了窗口实际长度是 right - left不需要再加一。很多人把第一版的 right - left 1 直接抄到精简版里就会在边界测试时发现答案比预期多 1。第三个 bug 是忘记考虑 k 为 0 的情况。k 为 0 时这道题退化成“找最长连续 1”的经典题。代码不需要任何特判只要正确处理 zeroCnt 和 while 收缩就能通过。但有些新手会特意写一个 if (k 0) 的分支反而容易在分支里设置错误的返回值。5.2 调试辅助打印每一轮的状态如果你发现输出不对最快的定位方式是在循环里临时加打印语句。一个比较实用的模式是打印 right、left、zeroCnt 和当前的 maxLen。for (int right 0; right numsSize; right) { if (nums[right] 0) { zeroCnt; } while (zeroCnt k) { if (nums[left] 0) { --zeroCnt; } left; } int len right - left 1; if (len maxLen) { maxLen len; } printf(r%d l%d z%d len%d max%d\n, right, left, zeroCnt, len, maxLen); }把打印结果和前面手动推演的表对照着看能很快定位到是哪一步的状态出了问题。定位之后记得把打印删掉避免提交时超时或者输出干扰。5.3 这道题可以怎么考你面试里除了让你写代码还经常追问几个问题。第一个是“为什么不能用贪心直接翻转最少的 0”原因是“最长连续 1”要求连续而翻转的 0 必须落在同一个连续区间里这个“同一个区间”的约束让贪心失效。你要找的不是“最少的 0”而是“包含不超过 k 个 0 的最长区间”。第二个追问是“还有没有其他解法”。这道题的标签其实包含二分、前缀和和滑动窗口。用前缀和统计 0 的个数然后对每个左端点二分查找右端点的最远位置可以做到 O(n log n)。面试时你可以先提这个思路再说滑动窗口能优化到 O(n)体现出你对复杂度优化的理解。第三个追问是“如果把 0/1 换成任意字符怎么做”。这个问题指向 LeetCode 424 题 Longest Repeating Character Replacement它的解法就是把“统计 0 的个数”推广成“统计窗口内出现次数最多的字符”当窗口长度减去最大出现次数超过 k 时收缩。1004 题其实可以看作 424 题在只有两类字符情况下的特例。6. 同类题迁移滑动窗口模板与刷题路线6.1 从 1004 到 424把 0/1 换成任意字符424 题的题面是给你一个字符串你最多可以替换 k 个字符让某个字符连续出现的长度尽可能长。粗看和 1004 没关系但抽象之后完全是一个模型。1004 里我们统计的是窗口里 0 的个数0 就相当于“要替换的坏字符”。424 里窗口可能有很多种不同字符我们需要知道窗口里“出现次数最多的那个字符”是多少记为 maxCnt那么窗口里其他字符的数量就是窗口长度减去 maxCnt。这个数量如果超过 k就必须收缩左边界直到其他字符的数量不超过 k。实现上的关键差异是 maxCnt 不能随便减小。因为滑动窗口收缩时某个字符的计数会减少但窗口里出现次数最多的字符可能已经不是之前那个了重新扫描窗口找最大值会让复杂度退化成 O(n²)。常规做法是只在加入字符时更新 maxCnt收缩时不回退。这个思路有点违反直觉但在“求最长合法窗口”的框架下是正确的因为 maxCnt 只影响收缩判断一个偏大的 maxCnt 会让窗口更难被收缩而我们要的是“依然尽可能长”。6.2 一套通用模板吃下多道题从 1004 里提炼出的三步模板可以套用到绝大多数滑动窗口题目上int left 0; for (int right 0; right n; right) { // 第 1 步把 nums[right] 纳入窗口状态 // 第 2 步当窗口不满足约束时收缩 left并同步移出状态 while (窗口不满足约束) { // 移出 nums[left] 对应的状态 left; } // 第 3 步此时窗口满足约束更新答案 }LeetCode 第 3 题 Longest Substring Without Repeating Characters 用的是这个模板只是窗口约束变成了“窗口内没有重复字符”状态需要用一个计数数组维护。第 209 题 Minimum Size Subarray Sum 也是这个模板只是求的是最短长度更新答案的位置和方式略微不同。第 2024 题 Maximize the Confusion of an Exam 几乎是 1004 的照搬把 0/1 换成 T/F 而已。如果按专题刷题建议顺序是485 题k0 的入门、1004 题k 为任意值的通用版、424 题字符替换的推广版、2024 题同构练习。顺着这个路线刷下来滑动窗口的“窗口状态维护”和“收缩时机”这两件事基本就练透了。6.3 模板之外我实际使用时的选择我自己刷题时会把第一版作为默认写法因为它在任何情况下都不会出逻辑错误。精简版虽然代码短但每次写之前都得在心里重新确认一遍“为什么可以不平移回合法状态”这在紧张的笔试环境里容易犹豫。第二版更像是一种思维训练理解了它你对滑动窗口的理解会上一个台阶但默写代码时没必要冒险。另外一个小技巧如果题目允许我习惯把 numsSize 先存下来避免在循环条件里反复访问参数变量。C 语言在 -O2 优化下这通常没区别但代码风格上更清晰。还有如果本地测试需要一次跑很多用例最好把测试数组的 size 显式写出来比如 int size sizeof(nums) / sizeof(nums[0])避免手数元素个数数错。我在实际面试中遇到过不止一次追问这道题每次能快速给出 O(n) 的滑动窗口解并且把“为什么 left 不需要回退”讲清楚的人基本都能让面试官满意。这题最大的价值不在于代码本身而在于它把“单调性带来双指针可行性”这个思想演示得非常干净。下次遇到看起来像“子数组最值”的问题先别急着枚举想想能不能用一条传送带把窗口维护起来。