文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载本文是 InterviewGuide 项目 精选力扣 300 题目之双指针 系列中对 LeetCode 1004 的完整题解。题目要求在一个 01 数组中最多把K个 0 翻转为 1求能得到的仅包含 1 的最长连续子数组长度。本文将完整复现阿秀解题时的三版代码暴力超时版 → 队列模拟滑窗失败版 → 双指针滑动窗口 AC 版逐段分析每一版的思路、缺陷与改进点帮你彻底掌握定长/限额型滑动窗口这一类高频面试题型的思考套路。一、题目回顾最多翻转 K 个 0求最长连续 1 子数组原题描述如下给定一个由若干0和1组成的数组A我们最多可以将K个值从 0 变成 1返回仅包含 1 的最长连续子数组的长度。示例 1输入A [1,1,1,0,0,0,1,1,1,1,0], K 2 输出6 解释 [1,1,1,0,0,1,1,1,1,1,1] 粗体数字从 0 翻转到 1最长的子数组长度为 6。示例 2输入A [0,0,1,1,0,0,1,1,1,0,1,1,0,0,0,1,1,1,1], K 3 输出10 解释 [0,0,1,1,1,1,1,1,1,1,1,1,0,0,0,1,1,1,1] 粗体数字从 0 翻转到 1最长的子数组长度为 10。提示1 A.length 200000 K A.lengthA[i]为0或11.1 关键转化把翻转翻译成窗口统计量最多把 K 个 0 变成 1本质上等价于我们只要找到一个最长的子数组其中 0 的个数不超过 K 个那么这 K 个 0 就都能被翻转为 1整个窗口内的元素就全是 1 了。于是问题就变成求最长的、满足窗口内 0 的个数 ≤ K的连续子数组长度。这也是这一类限额型滑动窗口问题的通用翻译手法——把复杂操作翻转、删除、替换抽象成对窗口内某个统计量的约束。1.2 约束条件透露的复杂度信号A.length最大可达 20000如果写出最坏情况O(n²)的算法例如枚举所有左右边界大约要执行 4×10⁸ 次基本操作在 C 环境下也极易超时实测就是超时见下文版本一。因此正解必须把复杂度压到O(n)或O(n log n)这直接指向滑动窗口 / 双指针。完整题目与示例见仓库文档 1004.最大连续1的个数III.md。二、版本一暴力枚举为什么超时第一版代码的思路是以每个位置为起点先数完起点后面连续的一段 1再尝试把最多 K 个 0 翻进去翻满 K 个之后再继续数尾巴上的 1取所有起点下的最大值。int longestOnes(vectorint A, int K) { if (A.size() K) return A.size(); size_t len A.size(); size_t temp0,result0,zeroCut0; for (size_t i 0; i len;i) { zeroCut 0; temp 0; while (i lenA[i] 1) { i; temp; } for (size_t j i; j len; ) { if (zeroCut KA[j] 0 ) { temp; zeroCut; j; } else if (zeroCut KA[j] 1 ) { temp; j; } if (zeroCut K) { while (jlen A[j] 1) temp; break; } } result max(result, temp); } return result; }2.1 为什么它慢先看外层循环的结构for循环的循环变量i又被内层while (i len A[i] 1)继续往后推也就是说外层循环实际上是按每一段连续 1 的起点在枚举左边界。对每个左边界内层for循环从当前位置j开始向右扫描每翻一个 0 走一步翻满 K 个 0 之后再额外数一段尾巴上的 1。这里存在两个问题重复扫描严重不同左边界对应的窗口大量重叠同一段元素会被反复遍历。例如示例 1 中起点在A[0]时会扫到A[4]起点在A[3]跳过一段 1后又会重新扫A[4]之后的所有元素重叠区域被重复计算。最坏复杂度是 O(n·K)当数组几乎全是 0、而 K 又接近 n 时每个左边界的内层扫描都要推进大约 K 个位置总操作量达到n × KK 接近 n 时即为O(n²)。在n 20000的上限下直接超时。仓库记录中该版本的结果就是超时了——它暴露了一个核心教训枚举起点是典型的重复劳动而滑动窗口的价值恰恰在于让每个元素只进出窗口一次把重复扫描消掉。三、版本二队列模拟滑窗卡在哪里第二版试图用queue模拟一个滑动窗口队列res里装窗口内元素temp记录窗口长度zeroCut记录窗口内 0 的个数当 0 的个数达到 K1 时就从队首弹出元素直到弹出第一个 0把 0 的数量压回 K。int longestOnes(vectorint A, int K) { if (A.size() K) return A.size(); size_t len A.size(); size_t temp0,result0,zeroCut0; queueint res; for (size_t i 0; i len;i) { if (A[i] 1) { res.push(1); temp; } else { res.push(0); temp; zeroCut; } if (zeroCut K) { result max(result, temp); } else if(zeroCutK1){ temp temp - 1; while (res.front() ! 0) res.pop();//直到遇到第一个0 res.pop();//将 0 pop出去 zeroCut K; result max(result, temp); temp res.size(); } } return result; }思路方向是对的想维持一个滑动的窗口但这版实现存在几个致命缺陷弹出过猛丢掉有效前缀当zeroCut变成 K1 时代码从队首一路弹出直到第一个 0 也被弹出去等于把第一个 0 之前的所有元素全部丢弃。可实际上合法的窗口只需要把 0 的个数压回 K弹出到第二个 0 之后才是正确的收缩量。这一版弹得太多窗口被错误地截短。拿示例 1A [1,1,1,0,0,0,1,1,1,1,0], K 2手工跑一遍最终会算出 10而正确答案是 6说明这版结果是错的。0 的个数不足 K 时 result 永不更新result只在zeroCut K或zeroCut K1两个分支里更新。如果整个数组的 0 总数不足 K 个例如A [1,1,1,1,1], K 3zeroCut永远达不到 Kresult一直停留在 0——而正确答案应该是整个数组的长度 5。计数与真实窗口错位temp temp - 1与temp res.size()的两次修正逻辑上自相矛盾导致temp并不等于队列res的真实长度后续迭代里temp与真实窗口大小对不上号。这个版本再次印证了滑窗问题的关键窗口的左端必须用索引指针来精确控制弹出多少、收缩到哪都要有明确依据用容器模拟反而让收缩逻辑变得含糊、易错。四、版本三滑动窗口双指针正解第三版是参考他人解法后理解、消化并复现的经典双指针写法也是本题的标准答案。仓库记录该版本提交数据为执行用时 56 ms、击败约 95.70% 的 C 提交内存消耗 13.8 MB、击败约 83.98% 的提交具体数据随提交时间与运行环境会有波动。int longestOnes(vectorint A, int K) { //count用来统计窗口中0的个数 int left 0, right 0, count 0, result 0, size A.size(); while (right size) { if(A[right]0) count 1; while (count K)//当窗口内0的个数大于K时需要缩小窗口 { if(A[left]0) count -1; left; } //窗口内0的个数小于等于k时也就是可以该窗口内的0都可以替换根据该窗口长度来确定是否更新result result max(result, right - left 1); right; } return result; }4.1 逐段拆解窗口扩张right指针负责向右扩展窗口。每次把A[right]纳入窗口如果是 0 就让count统计当前窗口内 0 的个数。窗口收缩一旦count K说明窗口内的 0 已经多到 K 次翻转也覆盖不了窗口非法必须从左端收缩。left每收缩一个位置如果移出去的元素是 0就count--直到count重新回到 K 以内。更新答案只要count K窗口 [left, right] 内的所有 0 都可以被翻转窗口长度right - left 1就是一个合法候选用result max(result, right - left 1)取最大值。4.2 正确性论证不变式循环每一步结束时窗口[left, right]内的 0 的个数都满足count K即窗口始终合法。最优性我们要求的是最长合法窗口。任何count K的窗口都是合法候选收缩只会让窗口变短、不会产生更优解所以只有当窗口非法count K时才收缩一旦合法就只扩张并更新答案。这种只收缩到合法为止、绝不额外收缩的策略保证不会漏掉最长窗口。单调性left和right都只会向右移动且left永远不会超过right。每个元素最多被right扫过一次、被left弹出过一次因此整体是O(n)。4.3 复杂度与边界情况时间复杂度O(n)每个元素最多进出窗口各一次。空间复杂度O(1)只用了几个整型变量相比版本二的queue省掉了整个窗口的存储。边界情况K 0退化成求最长连续 1 的个数即 LeetCode 485本代码自然成立——遇到 0 就收缩窗口永远是纯 1。K 数组中 0 的总数count永远不会超过 K窗口一路扩张到整个数组result即为数组长度与第一版里if (A.size() K) return A.size();的特判殊途同归。数组全为 1 或全为 0 时上述逻辑同样正确。五、仓库内同主题延伸阅读本题属于双指针/滑动窗口专题InterviewGuide 仓库的 双指针题单 中还有两道同主题题目可以串联学习485.最大连续1的个数easy不翻转任何 0只统计原始数组中连续 1 的最长段。它比本题少了一个翻转维度直接一趟遍历维护当前连续 1 的个数遇到 0 就重置。仓库解法中还特别提醒循环结束后别忘了再做一次result max(result, cut)因为数组末尾的一段连续 1 在循环内没有机会触发遇到 0 才更新的分支。对比 485 与 1004 会发现1004 的滑动窗口正是 485 思路在允许 K 个 0条件下的推广。1498.满足条件的子序列数目medium排序 双指针 幂预处理。先排序去掉子序列对顺序的要求再用左指针固定最小元素、右指针从后往前收缩找到最大合法元素配合预处理的 2 的幂数组统计组合数。它与本题共享两个指针按约束条件收缩窗口的核心骨架适合放在一起体会双指针的两类典型用法窗口滑动 vs. 对向收缩。六、小结这类题的面试要点翻译能力把翻转/替换/删除 K 个翻译成窗口内某统计量 ≤ K是解题第一步。窗口维护right负责扩张count K时left收缩到合法为止count K时更新答案——三件事顺序不能乱。复杂度证明能说清每个元素最多进出窗口各一次因此 O(n)是面试官最看重的部分。边界意识K 0、K大于等于 0 的总数、全 1/全 0 数组最好在写完后手动验一遍。赞分享文档教程知识库【免费下载链接】InterviewGuide「InterviewGuide」是阿秀从校园-职场多年计算机自学过程的记录以及学弟学妹们计算机校招秋招经验总结文章的汇总包括但不限于C/C 、Golang、JavaScript、Vue、操作系统、数据结构、计算机网络、MySQL、Redis等学习总结坚持学习持续成长项目地址https://gitcode.com/forthespada/InterviewGuide点击查看免费下载相关推荐刷穿 LeetCode1004. 最大连续1的个数 III——从动态规划到二分再到滑动窗口的完整推导刷穿 LeetCode1004. 最大连续1的个数 III——从动态规划到二分再到滑动窗口的完整推导 导读 本文是「刷穿 LeetCode」系列中 1004.教程文档自然语言指挥声音风格Parler-TTS 是怎么做到的自然语言指挥声音风格Parler TTS 是怎么做到的 给产品演示配一段旁白需求写的是低一点的女声、语速快、像在狭小房间里——但大多数开源 TTS 只语音AI 应用深度学习AlgoNote 题解精讲LeetCode 0485 最大连续 1 的个数——一次遍历统计法附 0487 / 1004 滑动窗口进阶AlgoNote 题解精讲LeetCode 0485 最大连续 1 的个数——一次遍历统计法附 0487 / 1004 滑动窗口进阶 导读 本文围绕「算法教程文档知识库上一篇终极指南sweetalert2/ngx-sweetalert2如何为Angular应用打造优雅弹窗体验下一篇探索DataMapper高效能数据映射工具创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考