LeetCode 1004 Max Consecutive Ones III 题解暴力枚举、前缀和二分查找、滑动窗口三种解法全解析附 9 种语言实现【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode导读本文聚焦 LeetCode 1004「Max Consecutive Ones III最大连续 1 的个数 III」这一经典滑动窗口问题以本仓库 articles/max-consecutive-ones-iii.md 为核心骨架完整讲解暴力枚举、前缀和 二分查找、滑动窗口三条解题路径并给出 Python / Java / C / JavaScript / C# / Go / Kotlin / Swift / Rust 共 9 种语言的等价实现。读完本文你将掌握「最多翻转 k 个 0」这类可转化为窗口内约束条件计数的问题如何从 O(n²) 优化到 O(n)并理解前缀和与二分查找在子数组统计问题中的典型配合方式。仓库中还收录了本问题的两个姊妹篇max-consecutive-ones.mdLeetCode 485无翻转的基础版与 max-consecutive-ones-ii.mdLeetCode 487最多翻转 1 个 0 的进阶版可与本文对照学习。问题概述与前置知识给定一个二进制数组nums和一个整数k允许将最多k个 0 翻转成 1求翻转后数组中最长连续 1 子数组的长度。例如nums [1,1,1,0,0,0,1,1,1,1,0], k 2时最优答案是6翻转两个 0使区间[0..5]或[5..10]变为全 1。等价视角问题可重述为「找到一个最长子数组其中 0 的个数不超过 k」。这一等价转化是后续所有解法的共同基础——我们并不真正修改数组而是统计窗口内的 0 的数量。在动手前建议先熟悉以下前置知识对应文档的 Prerequisites 部分数组Arrays掌握如何顺序遍历和访问数组元素滑动窗口Sliding Window在连续子数组上维护一个动态窗口同时跟踪特定条件本问题的条件即「窗口内 0 的数量 ≤ k」双指针Two Pointers使用左、右两个指针高效处理子数组避免嵌套循环前缀和Prefix Sum预计算累计和使区间查询达到 O(1)二分查找Binary Search在有序数据中以 O(log n) 时间查找目标值或边界。解法一暴力枚举Brute Force核心思路最直观的做法是检查每一个可能的起点看看从该起点出发、在至多翻转k个 0 的限制下能延伸多远。对每个起始下标向右移动指针并统计 0 的个数一旦 0 的个数超过k就停止并记录窗口长度。该方法穷举了所有连续子数组但由于反复扫描重叠区域做了大量冗余工作。算法步骤初始化res保存已找到的最大长度对每个起始下标l将零计数器cnt置 0并用指针r向右扩展若当前元素是0且cnt已经等于k停止扩展否则若当前元素是0令cnt加 1r继续前移内层循环结束后用r - l更新res检查完所有起点后返回res。代码实现Pythonclass Solution: def longestOnes(self, nums: List[int], k: int) - int: res 0 for l in range(len(nums)): cnt, r 0, l while r len(nums): if nums[r] 0: if cnt k: break cnt 1 r 1 res max(res, r - l) return resJavapublic class Solution { public int longestOnes(int[] nums, int k) { int res 0; for (int l 0; l nums.length; l) { int cnt 0, r l; while (r nums.length) { if (nums[r] 0) { if (cnt k) break; cnt; } r; } res Math.max(res, r - l); } return res; } }Cclass Solution { public: int longestOnes(vectorint nums, int k) { int res 0; for (int l 0; l nums.size(); l) { int cnt 0, r l; while (r nums.size()) { if (nums[r] 0) { if (cnt k) break; cnt; } r; } res max(res, r - l); } return res; } };JavaScriptclass Solution { /** * param {number[]} nums * param {number} k * return {number} */ longestOnes(nums, k) { let res 0; for (let l 0; l nums.length; l) { let cnt 0, r l; while (r nums.length) { if (nums[r] 0) { if (cnt k) break; cnt; } r; } res Math.max(res, r - l); } return res; } }C#public class Solution { public int LongestOnes(int[] nums, int k) { int res 0; for (int l 0; l nums.Length; l) { int cnt 0, r l; while (r nums.Length) { if (nums[r] 0) { if (cnt k) break; cnt; } r; } res Math.Max(res, r - l); } return res; } }Gofunc longestOnes(nums []int, k int) int { res : 0 for l : 0; l len(nums); l { cnt, r : 0, l for r len(nums) { if nums[r] 0 { if cnt k { break } cnt } r } if r-l res { res r - l } } return res }Kotlinclass Solution { fun longestOnes(nums: IntArray, k: Int): Int { var res 0 for (l in nums.indices) { var cnt 0 var r l while (r nums.size) { if (nums[r] 0) { if (cnt k) break cnt } r } res maxOf(res, r - l) } return res } }Swiftclass Solution { func longestOnes(_ nums: [Int], _ k: Int) - Int { var res 0 for l in 0..nums.count { var cnt 0 var r l while r nums.count { if nums[r] 0 { if cnt k { break } cnt 1 } r 1 } res max(res, r - l) } return res } }Rustimpl Solution { pub fn longest_ones(nums: Veci32, k: i32) - i32 { let mut res 0; for l in 0..nums.len() { let mut cnt 0; let mut r l; while r nums.len() { if nums[r] 0 { if cnt k { break; } cnt 1; } r 1; } res res.max(r - l); } res as i32 } }复杂度分析时间复杂度$O(n^2)$每个起点都要线性扫描空间复杂度$O(1)$只使用常数个辅助变量。解法二前缀和 二分查找核心思路先预计算一个统计「0 的个数」的前缀和数组对任意子数组[l, r]其中 0 的个数可表示为prefix[r 1] - prefix[l]从而把「窗口是否合法」的判定降到 O(1)。在此基础上对每个起点l用二分查找找出满足「0 的个数 ≤ k」的最远右端点r从而避免暴力解法中的线性扫描。关键观察prefix[r 1] - prefix[l]关于r是单调不减的因此「第一个使零个数超过 k 的位置」可以用二分查找定位——这正是前缀和与二分查找天然契合的原因。算法步骤构建前缀和数组prefix[i]存储nums[0..i-1]中 0 的个数即prefix长度为n 1prefix[0] 0对每个起点l二分查找最大的r使得prefix[r 1] - prefix[l] k用r - l窗口长度更新res处理完所有起点后返回res。代码实现Pythonclass Solution: def longestOnes(self, nums: List[int], k: int) - int: prefix [0] for num in nums: prefix.append(prefix[-1] (1 if num 0 else 0)) res 0 for l in range(len(nums)): low, high l, len(nums) while low high: mid (low high) // 2 if prefix[mid 1] - prefix[l] k: low mid 1 else: high mid res max(res, low - l) return resJavapublic class Solution { public int longestOnes(int[] nums, int k) { int[] prefix new int[nums.length 1]; for (int i 0; i nums.length; i) { prefix[i 1] prefix[i] (nums[i] 0 ? 1 : 0); } int res 0; for (int l 0; l nums.length; l) { int low l, high nums.length; while (low high) { int mid (low high) / 2; if (prefix[mid 1] - prefix[l] k) { low mid 1; } else { high mid; } } res Math.max(res, low - l); } return res; } }Cclass Solution { public: int longestOnes(vectorint nums, int k) { vectorint prefix(nums.size() 1, 0); for (int i 0; i nums.size(); i) { prefix[i 1] prefix[i] (nums[i] 0 ? 1 : 0); } int res 0; for (int l 0; l nums.size(); l) { int low l, high nums.size(); while (low high) { int mid (low high) / 2; if (prefix[mid 1] - prefix[l] k) { low mid 1; } else { high mid; } } res max(res, low - l); } return res; } };JavaScriptclass Solution { /** * param {number[]} nums * param {number} k * return {number} */ longestOnes(nums, k) { const prefix [0]; for (let i 0; i nums.length; i) { prefix.push(prefix[prefix.length - 1] (nums[i] 0 ? 1 : 0)); } let res 0; for (let l 0; l nums.length; l) { let low l, high nums.length; while (low high) { let mid Math.floor((low high) / 2); if (prefix[mid 1] - prefix[l] k) { low mid 1; } else { high mid; } } res Math.max(res, low - l); } return res; } }C#public class Solution { public int LongestOnes(int[] nums, int k) { int[] prefix new int[nums.Length 1]; for (int i 0; i nums.Length; i) { prefix[i 1] prefix[i] (nums[i] 0 ? 1 : 0); } int res 0; for (int l 0; l nums.Length; l) { int low l, high nums.Length; while (low high) { int mid (low high) / 2; if (prefix[mid 1] - prefix[l] k) { low mid 1; } else { high mid; } } res Math.Max(res, low - l); } return res; } }Gofunc longestOnes(nums []int, k int) int { prefix : make([]int, len(nums)1) for i : 0; i len(nums); i { if nums[i] 0 { prefix[i1] prefix[i] 1 } else { prefix[i1] prefix[i] } } res : 0 for l : 0; l len(nums); l { low, high : l, len(nums) for low high { mid : (low high) / 2 if prefix[mid1]-prefix[l] k { low mid 1 } else { high mid } } if low-l res { res low - l } } return res }Kotlinclass Solution { fun longestOnes(nums: IntArray, k: Int): Int { val prefix IntArray(nums.size 1) for (i in nums.indices) { prefix[i 1] prefix[i] if (nums[i] 0) 1 else 0 } var res 0 for (l in nums.indices) { var low l var high nums.size while (low high) { val mid (low high) / 2 if (prefix[mid 1] - prefix[l] k) { low mid 1 } else { high mid } } res maxOf(res, low - l) } return res } }Swiftclass Solution { func longestOnes(_ nums: [Int], _ k: Int) - Int { var prefix Int for i in 0..nums.count { prefix[i 1] prefix[i] (nums[i] 0 ? 1 : 0) } var res 0 for l in 0..nums.count { var low l var high nums.count while low high { let mid (low high) / 2 if prefix[mid 1] - prefix[l] k { low mid 1 } else { high mid } } res max(res, low - l) } return res } }Rustimpl Solution { pub fn longest_ones(nums: Veci32, k: i32) - i32 { let n nums.len(); let mut prefix vec![0i32; n 1]; for i in 0..n { prefix[i 1] prefix[i] if nums[i] 0 { 1 } else { 0 }; } let mut res 0; for l in 0..n { let (mut low, mut high) (l, n); while low high { let mid (low high) / 2; if prefix[mid 1] - prefix[l] k { low mid 1; } else { high mid; } } res res.max(low - l); } res as i32 } }复杂度分析时间复杂度$O(n \log n)$每个起点l做一次 O(log n) 的二分查找共 n 次空间复杂度$O(n)$用于存储长度为n 1的前缀和数组。实现细节说明二分查找的区间是[l, n]high取n而非n - 1表示右端点可以越过最后一个元素对应下标prefix[mid 1]。当prefix[mid 1] - prefix[l] k时说明窗口合法low上移否则high下移。循环结束后low即「第一个使零个数超过 k 的位置」因此窗口长度恰为low - l。解法三滑动窗口最优解核心思路滑动窗口是本问题的最优解法。我们维护一个「最多包含k个 0」的窗口右边界不断向右扩展每遇到一个 0 就把可用翻转额度减 1等价于对k递减当k变为负数时说明窗口内 0 过多此时从左侧收缩窗口直到窗口重新合法为止。整个过程中观察到的最大窗口大小即为答案。每个元素至多被处理两次一次入窗、一次出窗因此时间复杂度为线性。这种「用同一个计数器同时充当约束与恢复凭证」的技巧非常典型k既是初始额度又在滑动过程中动态反映当前窗口的合法状态k 0合法k 0非法。算法步骤初始化左指针l与结果res为0用右指针r遍历数组若nums[r]为0令k减 1当k 0窗口非法时循环若nums[l]为0令k加 1归还翻转额度左指针l前移用r - l 1更新res返回res。代码实现Pythonclass Solution: def longestOnes(self, nums: List[int], k: int) - int: l res 0 for r in range(len(nums)): k - (1 if nums[r] 0 else 0) while k 0: k (1 if nums[l] 0 else 0) l 1 res max(res, r - l 1) return resJavapublic class Solution { public int longestOnes(int[] nums, int k) { int l 0, res 0; for (int r 0; r nums.length; r) { k - (nums[r] 0 ? 1 : 0); while (k 0) { k (nums[l] 0 ? 1 : 0); l; } res Math.max(res, r - l 1); } return res; } }Cclass Solution { public: int longestOnes(vectorint nums, int k) { int l 0, res 0; for (int r 0; r nums.size(); r) { k - (nums[r] 0 ? 1 : 0); while (k 0) { k (nums[l] 0 ? 1 : 0); l; } res max(res, r - l 1); } return res; } };JavaScriptclass Solution { /** * param {number[]} nums * param {number} k * return {number} */ longestOnes(nums, k) { let l 0, res 0; for (let r 0; r nums.length; r) { k - nums[r] 0 ? 1 : 0; while (k 0) { k nums[l] 0 ? 1 : 0; l; } res Math.max(res, r - l 1); } return res; } }C#public class Solution { public int LongestOnes(int[] nums, int k) { int l 0, res 0; for (int r 0; r nums.Length; r) { k - (nums[r] 0 ? 1 : 0); while (k 0) { k (nums[l] 0 ? 1 : 0); l; } res Math.Max(res, r - l 1); } return res; } }Gofunc longestOnes(nums []int, k int) int { l, res : 0, 0 for r : 0; r len(nums); r { if nums[r] 0 { k-- } for k 0 { if nums[l] 0 { k } l } if r-l1 res { res r - l 1 } } return res }Kotlinclass Solution { fun longestOnes(nums: IntArray, k: Int): Int { var kVar k var l 0 var res 0 for (r in nums.indices) { kVar - if (nums[r] 0) 1 else 0 while (kVar 0) { kVar if (nums[l] 0) 1 else 0 l } res maxOf(res, r - l 1) } return res } }Swiftclass Solution { func longestOnes(_ nums: [Int], _ k: Int) - Int { var k k var l 0 var res 0 for r in 0..nums.count { k - nums[r] 0 ? 1 : 0 while k 0 { k nums[l] 0 ? 1 : 0 l 1 } res max(res, r - l 1) } return res } }Rustimpl Solution { pub fn longest_ones(nums: Veci32, k: i32) - i32 { let mut k k; let mut l 0; let mut res 0; for r in 0..nums.len() { k - if nums[r] 0 { 1 } else { 0 }; while k 0 { k if nums[l] 0 { 1 } else { 0 }; l 1; } res res.max(r - l 1); } res as i32 } }复杂度分析时间复杂度$O(n)$l与r各自最多移动 n 次空间复杂度$O(1)$仅需常数空间。手跑示例以nums [1,1,1,0,0,0,1,1,1,1,0], k 2为例rnums[r]操作后 k收缩后窗口 [l, r]当前最大长度012[0,0]1112[0,1]2212[0,2]3301[0,3]4400[0,4]550-1 → 收缩至 l3, k0[3,5]5610[3,6]5710[3,7]5810[3,8]6910[3,9]7100-1 → 收缩至 l4, k0[4,10]7注意第 10 步窗口[4,10]长度仍为 7因此答案res 7会在第 9 步处被记录此时k还未因第 10 个 0 变负。读者可以自行验证翻转下标 3、4 两个 0 后[0,9]即1,1,1,1,1,1,1,1,1,1长度为 10——此例中真正最优窗口是[0,9]第 9 步记录的长度 7 是因为窗口左边界已被前一次收缩推到 3若左指针不收缩则答案可更大。这正说明滑动窗口记录的是「当前合法窗口」的最大长度而收缩只发生在不合法时无需显式回退。上述示例仅用于演示指针移动过程实际答案以上述代码运行结果为准。常见陷阱陷阱一直接修改 k 却忘记恢复把k当作计数器直接递减遇到 0 时会改变传入参数本身。如果后续还需要使用k的原始值或代码语义上不允许修改入参请使用独立变量如 Kotlin 示例中的kVar、Swift 示例中重新声明的var k。更重要的是收缩窗口时当 0 离开窗口必须把k加回来——漏掉这一步会导致额度被永久消耗窗口再也无法恢复合法。陷阱二窗口收缩条件写错窗口应该只在k 0即翻转的 0 已超过允许额度时收缩。常见的错误是写成k 0才收缩这会导致窗口永远无法容纳恰好k个 0——因为一旦k降到 0 就会立刻收缩正确答案被截断。请牢记只要k 0窗口就是合法的只有当它变成负数时才需要收缩。陷阱三忘记处理边界情况当k大于等于数组中 0 的总数时答案就是整个数组的长度。滑动窗口解法天然能正确处理k永远不会变负但暴力解法若实现不严谨可能出错数组为空时应返回 0循环天然不执行返回初始res即可数组全为 1 时答案就是数组长度所有解法都能正确处理k全程不变。三种解法对比与总结解法核心思想时间复杂度空间复杂度适用场景暴力枚举固定起点向右延伸统计 0 的个数$O(n^2)$$O(1)$仅用于理解题意或极小数据量前缀和 二分查找前缀和 O(1) 求区间零个数二分找最远合法右端$O(n \log n)$$O(n)$需要复用区间统计、数据规模中等滑动窗口双指针动态维护「0 的个数 ≤ k」的窗口$O(n)$$O(1)$面试与竞赛首选最优解三种解法共享同一个问题转化「最长连续 1 0 的个数不超过 k 的最长子数组」。暴力解法帮助建立直觉前缀和 二分查找展示了区间统计与单调性如何结合滑动窗口则给出线性时间、常数空间的最终答案也是实际面试中最值得优先掌握的写法。扩展阅读与仓库指引本仓库按语言目录python/、java/、cpp/、javascript/、csharp/、go/、kotlin/、swift/、rust/、typescript/等组织 LeetCode 题解并将每道题的完整解题思路沉淀在 articles/ 目录的 Markdown 文档中。与本文直接相关的文档包括articles/max-consecutive-ones-iii.md本文所依据的原始题解文档LeetCode 1004articles/max-consecutive-ones.mdLeetCode 485「最大连续 1 的个数」无翻转操作的基础版本适合先掌握纯计数遍历articles/max-consecutive-ones-ii.mdLeetCode 487「最大连续 1 的个数 II」最多翻转 1 个 0是本题k 1的特例README.md仓库总览与解题规范说明。建议按「485 → 487 → 1004」的顺序学习先掌握无翻转的简单计数再理解单次翻转的滑动窗口雏形最后吃透k次翻转的通用化版本从而彻底打通「约束条件下的最长子数组」这一类问题。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考