LeetCode 每日一题打卡到 3719 这道“最长平衡子数组 I”时很多人第一反应是被题目标题里的“暴力枚举”逗笑了——官方都明示让你暴力了那还犹豫什么。但真正动手写的时候连续踩坑的人并不少。这道题本质上是一个比较经典的子数组判定问题给定一个只包含 0 和 1 的数组要找一个最长的连续子数组要求子数组里的 0 全部排在 1 的前面并且 0 和 1 的数量相等。它适合所有刚接触子数组类题目的同学也适合想复习“枚举起点终点 合法性检查”这套基本功的人。下面我会用暴力枚举为主线把完整的判定逻辑、代码实现、复杂度分析和进阶解法都过一遍文章最后还会整理我实际写代码时踩过的坑。1. 题目拆解先搞清楚平衡子数组到底长什么样1.1 从标题和题面提取关键约束先别急着写代码把题目里几个关键词一一拆开看。“最长”意味着我们最终要输出一个长度值所以代码里至少要有一个变量 ans 维护当前找到的最大长度初始化为 0每找到一个合法区间就尝试更新。“子数组”强调连续也就是说只能取原数组中相邻的一段不能像子序列那样跳跃着选元素也不能排序之后重新拼一段。“平衡”这两个字是整道题的核心。顺着题目的意思平衡子数组必须满足两个条件第一所有的 0 都出现在所有 1 的前面即数组形态只能是 000…000111…111 这种两段式第二0 的个数和 1 的个数必须相等。举个反例[0, 1, 0, 1] 里 0 和 1 的数量确实相同但第 3 个元素 0 出现在第 2 个元素 1 的后面顺序不满足所以它不是平衡子数组。题目末尾的“I”也很关键。这种命名方式一般代表同一个系列里的基础版本暗示数据范围不会给得很大暴力枚举足够通过。后续如果出现“II”通常意味着数据范围被放大逼着你换更优的算法。而标题里直接写明“暴力枚举”基本就是出题人在告诉你别多想枚举所有可能的子数组一个个检查就完事了。这里要提醒一点子数组问题最忌讳“全局统计”。比如你统计出整个数组有 4 个 0 和 4 个 1然后兴奋地认为答案至少是 8这在多数情况下是错的因为顺序约束会直接把你这个想法否决掉。必须先确认一段区间内部的相对顺序才有资格谈数量相等。1.2 平衡子数组的判定条件要判断一段区间 [l, r] 是否是平衡的需要同时满足三个条件。第一个条件区间的第一个元素必须是 0即 nums[l] 0。如果区间以 1 开头后面的元素无论怎么排都不可能做到“0 都在 1 前”因为开头那个 1 已经是 1 了而后面如果出现 0就是 1 后面跟着 0直接违规如果后面全是 1那就没有 0数量不相等同样不合法。第二个条件区间中不能出现“1 后面又跟着 0”的逆序结构。用一个布尔变量 hasOne 来标记即可遍历区间时遇到 0如果 hasOne 已经是 true说明已经出现过 1 了现在又看到 0直接判定这段区间非法遇到 1就把 hasOne 置为 true同时累加 1 的个数。第三个条件区间中 0 的个数等于 1 的个数并且数量大于 0。这个条件看起来简单但经常有人漏掉“数量大于 0”这一点导致把全 0 区间误判为合法。全 0 区间里 zeros 和 ones 都是 0如果不做额外判断zeros ones 是成立的这就错了。这三个条件合在一起等价于区间可以被严格切成一个全部由 0 组成的连续前缀和一个全部由 1 组成的连续后缀且两段长度相等。把“第一个 1 出现的位置”当作分界点来理解会更直观。不过代码实现上用 hasOne 标记法更自然因为它一边遍历一边检查不容易漏掉逆序情况。1.3 为什么暴力枚举是这一题最稳的开局暴力枚举的核心思路非常直白枚举所有可能的左端点 l再枚举所有可能的右端点 r对每一个区间做一次合法性检查通过则用区间长度更新答案。这个做法的时间复杂度是 O(n^3)枚举左右端点是 O(n^2)检查区间内部最多要遍历 O(n) 个元素合在一起就是 O(n^3)。空间复杂度是 O(1)只用几个临时变量。可能有人会问O(n^3) 这种复杂度也敢用答案是这题标题里已经写了“暴力枚举”说明数据规模一定在暴力可过的范围内。如果 n 是 50O(n^3) 大概是 12.5 万次操作瞬间出结果如果 n 是 200也才 800 万次操作1 秒内毫无压力就算 n 到 500三重循环也就 1.25 亿次操作在 O2 优化下通常也能过。从比赛和工程的角度来说拿到题先看数据范围再决定算法是比盲目套模板更重要的事情。暴力解法的最大价值就是“不容易错”。第一题求稳比求快更重要能用三重循环解决的事情就不要在编码的 5 分钟里冒险设计复杂的状态机。等 AC 之后再慢慢想优化也不迟。2. 暴力枚举的完整实现2.1 枚举思路与三种常见写法暴力枚举本身也有几种实现层次从最朴素到带各种剪枝实际效果差别不小。写法一最朴素的 O(n^3)。直接枚举左端点 l枚举右端点 r对 [l, r] 做一次完整遍历检查。逻辑最清晰适合讲解和验证思路但会做很多无意义的工作。比如区间长度不是偶数的情况其实根本不需要检查比如当前区间长度已经小于已知答案检查了也白检查。写法二带剪枝的 O(n^3)。在写法一的基础上增加两个剪枝左端点 nums[l] 不为 0 时直接跳过因为平衡子数组必须以 0 开头区间长度不是偶数、或者长度不超过当前 ans 时直接跳过因为不可能是更优答案。这两个剪枝在实际运行中能砍掉大量无效区间让真实耗时远低于理论上限。写法三枚举分界点。枚举 0 段和 1 段的分界位置然后向左右两侧扩展分别统计连续 0 和连续 1 的数量用 min(zeros, ones) * 2 更新答案。这种写法已经接近线性解法了虽然还带着枚举的影子但效率远高于前两种。如果题目要求的核心是“暴力”我的建议是掌握前两种第三种留作进阶思考。下面这段 C 代码是写法二的具体实现也是我在实际提交里最常用的一版class Solution { public: int longestBalancedSubarray(vectorint nums) { int n nums.size(); int ans 0; for (int l 0; l n; l) { // 剪枝平衡子数组必须以 0 开头 if (nums[l] ! 0) { continue; } for (int r l 1; r n; r) { int len r - l 1; // 剪枝平衡子数组长度必须是偶数且要比当前答案长 if (len % 2 ! 0 || len ans) { continue; } int zeros 0, ones 0; bool hasOne false; bool valid true; for (int k l; k r; k) { if (nums[k] 0) { if (hasOne) { valid false; break; } zeros; } else { hasOne true; ones; } } if (valid zeros ones) { ans len; } } } return ans; } };这里有一个细节len % 2 ! 0 的判断其实不是必须的因为就算长度是奇数只要 zeros 和 ones 相等长度就一定是偶数。但提前判断能省掉一次循环检查属于典型的“微优化”在数据量大一点的时候效果明显。len ans 则是更关键的一个剪枝毕竟找的是“最长”比当前答案还短的区间没有检查的必要。Python 版本也很容易写和 C 逻辑完全对应class Solution: def longestBalancedSubarray(self, nums: List[int]) - int: n len(nums) ans 0 for l in range(n): if nums[l] ! 0: continue for r in range(l 1, n): length r - l 1 if length % 2 or length ans: continue zeros 0 ones 0 has_one False valid True for k in range(l, r 1): if nums[k] 0: if has_one: valid False break zeros 1 else: has_one True ones 1 if valid and zeros ones: ans length return ans如果你平时用 Java结构也是一样的外层双循环内层用一个 check 函数封装上面的 hasOne 判断然后从主流程里调用。我个人觉得把 check 抽成独立函数更容易阅读但放在循环里会快一点点因为少了一次函数调用开销。竞赛里我一般直接写在循环里日常练习则更推荐抽函数。2.2 用一个例子一步步推演拿 nums [0, 0, 1, 1, 0, 1] 来手动跑一遍流程看看剪枝和判定是怎么协同工作的。开始前 ans 0。l 0nums[0] 0合法起点。r 1区间 [0, 0]len 2偶数但长度 2 0进入检查zeros 2ones 0hasOne 始终为 falsevalid true但 zeros ! ones所以不更新。r 2len 3奇数直接跳过。r 3区间 [0, 0, 1, 1]len 4进入检查遍历到第 3 个元素时 hasOne 变为 true后面两个都是 1没有逆序。zeros 2ones 2合法ans 更新为 4。r 4len 5奇数跳过。r 5区间 [0, 0, 1, 1, 0, 1]len 6进入检查前四个元素正常zeros 2ones 2hasOne true遍历到第 5 个元素 0 时发现 hasOne 为 true说明出现了“1 后面跟着 0”valid 置为 falsebreak。整个区间非法。然后 l 1nums[1] 0合法起点。r 2区间 [0, 1]len 2虽然合法但 len ans2 4直接跳过。r 3len 3奇数跳过。r 4len 4但 len ans跳过。r 5len 5奇数跳过。这一轮一个完整的检查都没做全靠剪枝挡住了。l 2nums[2] 1直接 continue。l 3nums[3] 1continue。l 4nums[4] 0合法起点。r 5区间 [0, 1]len 2但 len ans跳过。最后输出 ans 4。从这个例子能明显看出剪枝的价值一旦 ans 更新为 4后续长度不超过 4 的区间全部被挡在检查之外实际执行的操作远低于 O(n^3) 的理论复杂度。2.3 时间复杂度与空间复杂度分析从理论上讲这个解法的时间复杂度是 O(n^3)空间复杂度 O(1)。但实际运行时间会因为三个剪枝大幅缩短。首先是左端点剪枝所有以 1 开头的左端点直接跳过大约能省掉一半的枚举量。其次是长度剪枝长度不是偶数、或者长度不超过当前 ans 的区间不检查这在大数据量下能砍掉大量无效区间。最后是提前退出遍历区间时一旦发现逆序“1 后跟 0”立刻 break不需要检查完整个区间。不过极端情况下这个复杂度是会退化的。比如数组全是 0[0, 0, 0, ..., 0]。此时所有左端点都以 0 开头所有区间都没有逆序每个区间都会完整遍历。而且因为没有 1ans 始终为 0长度剪枝几乎不起作用复杂度就是严格的 O(n^3)。遇到这种卡常用例最直接的办法是在代码开头加一个特判如果数组里没有任何一个 1直接返回 0。这个特判同时也省去了一开始对“全 0 区间”误判的担忧算是一举两得。3. 从暴力到线性进阶解法的思路跃迁3.1 按连续段扫描的线性解法如果这道题将来出成“II”把 n 拉到 10^5 甚至 10^6O(n^3) 就彻底没戏了。好在这道题的结构非常有特点合法平衡子数组只能是“连续 0 段 连续 1 段”。基于这一点可以把数组看成一段一段交替出现的 0 和 1然后只在相邻两段里找答案。具体做法是i 0 ans 0 while i n: 统计从 i 开始连续 0 的个数 zeros 统计紧接着连续 1 的个数 ones ans max(ans, min(zeros, ones) * 2) i 移动到这段 1 的后面为什么只考虑相邻的 0 段和 1 段原因很简单如果合法区间跨越了两段以上必然会出现“0 段、1 段、0 段”或者“1 段、0 段”这样的结构。以“0 段、1 段、0 段”为例后面的 0 段出现在前面的 1 段之后已经违反了“0 都在 1 前”的顺序约束所以非法。剩下的合法候选只能是从某个 0 段开始到紧接着的 1 段结束。在每一对相邻的“0 段 1 段”里0 的个数是 zeros1 的个数是 ones。由于子数组可以不使用整段最多能取 min(zeros, ones) 个 0 和同样数量的 1拼出长度为 2 * min(zeros, ones) 的平衡子数组。还是用 [0, 0, 1, 1, 0, 1] 来验证。第一对段zeros 2ones 2ans max(0, 4) 4。第二对段zeros 1ones 1ans max(4, 2) 4。最终结果 4和暴力枚举得到的结果一致。线性解法的实现很短但它要求你心里已经很清楚“合法子数组的形态限制”。所以我反复强调第一遍刷题先用暴力把逻辑跑通再尝试优化。如果你跳过暴力直接上线性解一旦思路错了排查起来比暴力麻烦得多。3.2 暴力枚举与线性解法的差异对比把两种解法放在一起看差异还挺明显的我整理了一张表维度暴力枚举线性扫描时间复杂度O(n^3)O(n)空间复杂度O(1)O(1)实现难度低思路直接中需要理解段结构适用数据规模n ≤ 500 左右任意规模容错率高不容易想错中边界条件容易漏适合场景第一遍学习、比赛求稳数据量大、追求通过效率从这个对比能看出来写不写优化主要取决于数据范围。很多人刷题有个误区不管三七二十一上来就写“最优解”结果边界条件处理不好反而卡了很久。我个人的建议是周赛第一题看完数据范围允许暴力直接暴力等 AC 了如果还有余力再想想能不能优化到 O(n)。这样既保证了拿分又完成了学习。3.3 什么时候该写暴力什么时候该想优化判断标准其实很统一先看 n 的大小和时限。一般经验值如下n ≤ 5000O(n^2) 可行n ≤ 500 甚至更小O(n^3) 通常可行n ≤ 10^5 或 10^6必须 O(n log n) 或 O(n)。回到这道题题目标题明确写了“暴力枚举”那就是出题人在暗示你数据范围不会太大。如果这是比赛里的第一题我建议直接暴力把时间留给后面的题目。我见过不少选手在 Q1 上花 20 分钟设计 O(n) 解法最后 AC 了但 Q2/Q3 因为时间不够没写完。第一题求快第二三题求稳这才是竞赛策略。而“每日一题”的日常练习里暴力枚举反而能把子数组的基本功练扎实枚举、剪枝、判重、更新答案这些都是后面所有子数组题型的通用步骤。4. 常见坑与排查技巧4.1 高频错误速查表我自己在刷这道题的时候包括围观别人的讨论串下面这几种错误出现频率最高整理成一张速查表错误现象原因修复方式答案是 0 但手算应该有答案判断条件写错比如没有检查 nums[l] 0左端点必须以 0 开头把 [0, 1, 0, 1] 算成 4没有检查“1 后不能有 0”用 hasOne 标记顺序把 [0, 0] 算成合法只检查 zeros ones 但数量为 0更新答案前确认 zeros 0输出是奇数长度忘了平衡子数组一定是偶数长度长度剪枝 length % 2暴力写法超时剪枝不够所有区间都完整检查增加长度剪枝、左端点剪枝、提前 break全 0 用例超时没有 1所有区间都完整遍历特判没有 1 的数组直接返回 0这里最容易被忽视的是第三条。如果区间只有 0 没有 1zeros 和 ones 都是 0zeros ones 是成立的。很多人写完代码拿 [0, 1] 一测没问题但拿 [0, 0] 一测发现居然返回长度 2当场愣住。修复方式很简单在更新答案前确认 zeros 0 ones 0或者用长度必须是偶数且至少为 2 这个隐含条件来兜底。4.2 测试用例设计方法刷题的时候设计一组好的测试用例能帮你快速定位错误。针对这道题我建议至少覆盖以下 8 类最简单用例nums [0, 1]答案 2。逆序用例nums [1, 0]答案 0。全 0 用例nums [0, 0, 0]答案 0。全 1 用例nums [1, 1, 1]答案 0。完全平衡用例nums [0, 0, 0, 1, 1, 1]答案 6。交替用例nums [0, 1, 0, 1, 0, 1]答案 2。多段混合用例nums [0, 0, 1, 1, 0, 1]答案 4。边界用例nums [0] 或 nums [1]答案 0。把这些用例在本地或者在线 IDE 里跑一遍能过滤掉绝大多数逻辑错误。特别是第 6 个交替用例很多人在没有正确顺序判断的情况下会输出 6这就是踩了“以为只要 0 和 1 数量相等就行”的坑。第 3 和第 4 个用例则专门用来验证“数量大于 0”这个条件。4.3 这类子数组题的通法总结“最长平衡子数组”“最长回文子串”“最长连续相同元素子数组”这类问题其实共享一套刷题框架明确子数组的合法性定义把它抽象成可以用代码表达的条件。根据数据范围确定枚举方式小数据暴力枚举大数据考虑双指针、前缀和、动态规划或状态压缩。先写一个最直观的版本确认逻辑正确再考虑优化。用边界用例和目标形态的用例验证。暴力枚举看似笨但在处理“子数组类别”的问题时它其实是很好的思维起点。很多看似复杂的问题比如题目相关搜索里出现的“目标和”“爱吃香蕉的狒狒”这类题最终解法本质上也是把暴力思路一步步推导、优化出来的。暴力枚举不是终点但它是通向更优解的起点。我自己在刷这道题的时候第一次提交其实翻车了我写的判断逻辑只统计了 zeros 和 ones 的数量完全没有检查顺序结果把 [0, 1, 0, 1] 判成了合法答案是 4。后来补上 hasOne 标记又发现全 0 用例返回了 0而不是我以为的 2排查时才意识到自己压根没考虑“0 和 1 的数量都要大于 0”这个隐含条件。这两个错误都不难修但如果不设计测试用例很难一眼看出来。所以最后再分享一个小技巧遇到子数组判定类问题先把最朴素的 check 函数写出来把所有条件集中在一个函数里再用不同形态的测试用例去验证。等 check 逻辑确认无误后再把它塞进双层循环或三层循环里找答案。这样哪怕后面出问题嫌疑范围也能缩小到枚举逻辑本身而不是判定逻辑。这种分层的做法是我刷子数组题最受用的一条习惯。