前几天在OJ上刷到一道叫“非常男女”计划的老题。题目很短但不少第一次见的人会卡住给你一个长度为 n 的 0/1 序列0 和 1 分别代表两种性别要求找出最长的连续区间让区间里 0 和 1 的数量恰好相等。这道题表面是个“匹配”故事本质却是一个经典算法模型——前缀和配合哈希表求“最长连续子段和为 0”。如果你最近在练前缀和、Map 的用法或是准备笔试里常见的数组子区间问题很值得把它吃透。我最早做这道题时也绕了一段弯路第一反应写了个 O(n^2) 的前缀和暴力结果数据一大直接超时。后来把思路换成“记录前缀和第一次出现的位置”代码很短跑起来却非常稳。这篇就把完整思路、Java 实现、以及我踩过的坑一次性说清楚。1. 先弄明白题目在找什么1.1 把“男女配平”翻译成数学条件题目里的连续区间可以理解成“在一条队伍中随便截取连续的一段”。假设这一段里有 x 个 0y 个 1题目要求的是 x y。这个条件看似简单但处理起来有个隐蔽的难点0 和 1 是两种离散状态你没办法像做一般的子数组求和那样直接套用“当前区间和等于某个目标值”的模板。很多人第一反应是暴力枚举所有的左端点和右端点然后统计中间 0 和 1 的个数复杂度 O(n^3)显然不可取稍微优化一点先用前缀和预处理出 0 的数量和 1 的数量再枚举左右端点复杂度降到 O(n^2)但 n 一旦到了十万级别依然会超时。所以必须换思路。关键点在于x y 这个条件等价于“x - y 0”。如果我们能给每个数字重新赋一个权重让 0 和 1 的贡献相反那么“两种数量相等”就变成了“区间内权重和为 0”。这可比分别统计两种数量优雅得多。我一般习惯这样定义遇到 0 记作 -1遇到 1 记作 1。当然反过来也行具体哪个对应男生、哪个对应女生不重要重要的是让两种值在求和时互相抵消。只要这两个值互为相反数问题性质就完全一样。1.2 为什么滑动窗口在这里不灵很多同学看到“连续子段”“最长”这两个词第一反应就是滑动窗口。我开始也这么想过但很快发现这题不能用双指针。原因在于滑动窗口正常运行的前提是“单调性”窗口变大或缩小时我们关心的指标要能判断出该不该收缩左边界。比如求最长无重复字符的子串右指针往前走遇到重复字符时窗口一定不合法必须收缩左边界直到合法这个过程是确定的。但这道题里你没办法判断右指针往前移动后左指针到底该不该动。举个例子。假设当前窗口 [left, right] 里 0 的数量比 1 多 2 个右指针继续往右走如果遇到一个 1差值会变成 1窗口变得更接近合法这时候你如果按“不合法就收缩左边界”的逻辑去处理反而可能丢掉一个更长的合法区间。反过来一个已经合法的窗口右指针加一个 0 进来差值变成 -1又变得不合法了但你无法保证后面再加几个 1 会不会再次平衡。也就是说差值变化是双向的窗口扩大不一定让条件更差窗口缩小也不一定让条件更好。这种情况下双指针就没有单调性可言强行滑动窗口会漏掉正确答案。所以这道题必须放弃“用指针维护一个当前窗口”的直觉转而用前缀和来做。2. 核心思路把问题变成“前缀和出现相同值”2.1 重新编码让 0 和 1 变成相反数先把输入的每个数字做一次映射0 变成 -11 变成 1。例如序列0 1 0 0 1 1转换后就是-1 1 -1 -1 1 1这样做的好处是任意一个区间内如果 0 和 1 数量相等那么转换后的数字相加必然为 0。因为假设区间里有 a 个 0、a 个 1那么区间总和就是 a×(-1) a×(1) 0反过来如果区间总和是 0设 0 的个数为 x1 的个数为 y则总和是 -x y等于 0 时只能推出 x y。所以这道题等价于在转换后的数组中找一个最长的连续子数组使得子数组的和为 0。这个等价关系一旦建立问题就清爽了许多。接下来需要解决的就是一个很经典的子问题怎么高效判断并找出“和为 0 的最长连续子数组”。2.2 区间和如何用前缀和表示为了快速计算任意区间的和我们引入前缀和数组 pre。定义方式如下pre[0] 0表示前 0 个元素的和pre[i] pre[i-1] 转换后的第 i 个元素其中 i 从 1 开始。于是数组 pre[i] 表示“前 i 个元素转换后的总和”。任何一个区间 [l, r] 的和都可以用两个前缀和做减法得到sum(l, r) pre[r] - pre[l-1]如果要求某个区间和为 0也就是pre[r] - pre[l-1] 0化简就是pre[r] pre[l-1]这句话才是整道题的核心如果在前缀和数组中两个位置的值相等那么这两个位置之间的原始区间0 和 1 的数量一定相等。不信可以拿一个简单例子试。假设原序列是0 1 0 1转换后是-1 1 -1 1前缀和依次是pre[0] 0pre[1] -1pre[2] 0pre[3] -1pre[4] 0注意 pre[0]、pre[2]、pre[4] 都等于 0。pre[0] 到 pre[2] 之间夹的是前两个元素即 0 1中间正好一男一女合法pre[0] 到 pre[4] 之间是全部四个元素0 1 0 1也合法长度是 4。pre[2] 到 pre[4] 之间是后两个元素 0 1同样合法。再比如 pre[1] 和 pre[3] 都等于 -1它们之间夹的是第 2 到第 3 个元素也就是 1 0也合法。所以现在问题被彻底改写了我们要在所有满足 pre[i] pre[j] 的 i j 中找 j - i 最大的那一对。这个最大差值就是答案。2.3 用 Map 记录“第一次出现的位置”既然要最大化 j - i那么当我们要比较前缀和相同的两个位置时自然希望 i 越小越好、j 越大越好。我们可以从左到右扫描一遍原始数组同时维护当前前缀和 sum。每到一个新位置 i就看一下当前 sum 在之前是否出现过如果出现过说明从“第一次出现的位置”到现在的 i 这一段是合法的长度 i - firstPosition如果没出现过就把当前 sum 和当前位置记录进哈希表注意这个位置将成为未来所有相同 sum 的比较基准。这里最关键的细节是哈希表里存的一定是“最早出现的位置”而不是最近出现的位置。因为两个相同前缀和之间夹出来的区间都是合法区间我们要的是最长距离用最早位置去减才能得到最大长度。还是上面的例子遇到 pre[4] 0 时哈希表里 0 最早出现在位置 0所以算出长度 4 - 0 4正好是整段序列最长合法区间。如果错误地把位置 2 当成 0 的基准算出来就只有 4 - 2 2答案就会偏小。另外要注意前缀和完全可能是负数尤其是把 0 变成 -1 之后前缀和会在负数区间频繁出现。用 Java 的 HashMap 来存键值对就不用担心负数下标问题这是比直接用数组做偏移量更省心的地方。3. Java 代码怎么写才不容易错3.1 完整可提交的代码把上面的思路落成 Java 代码核心逻辑其实只有十来行。完整版本如下import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); MapInteger, Integer firstPos new HashMap(); // 空前缀和 0 的下标是 0必须初始化 firstPos.put(0, 0); int sum 0; int ans 0; for (int i 1; i n; i) { int x sc.nextInt(); // 0 看成 -11 看成 1 sum (x 1 ? 1 : -1); if (firstPos.containsKey(sum)) { ans Math.max(ans, i - firstPos.get(sum)); } else { firstPos.put(sum, i); } } sc.close(); System.out.println(ans); } }一个常见的写法是把数组先存下来再跑第二遍循环。但这题其实完全不用存原始数组因为边读边算已经足够。这样既省内存代码也更紧凑。提交时记得类名必须是 Main不要带 package 声明在大多数 OJ 上用 Scanner 读十万级数据完全没问题不需要额外引入更复杂的快速输入类。3.2 初始化与边界处理代码里最容易被忽略的一行就是firstPos.put(0, 0)。如果不放这一行那么当前缀和首次回到 0 时你是找不到基准位置的。举例来说序列只有两个数1 0转换后是 1 -1前缀和是 pre[0]0、pre[1]1、pre[2]0。正确结果应该是 2因为整个区间里 1 和 0 数量相等。计算过程是扫描到 i2 时 sum0此时能够在 Map 里查到 0 的第一次位置是 0于是 ans2-02。如果没初始化Map 里没有 0 这个键sum0 会被当成第一次出现最终答案变成 0直接 WA。另一个边界是如果整个序列无论如何都无法配平比如全 0 或者全 1那么最终答案就是 0。代码里 ans 的初始值是 0这种情况下自然输出 0不需要额外特判。循环里的下标也建议从一开始写一直写到 n因为前缀和 pre[i] 表示前 i 个元素。这样和“位置 0 代表空前缀”的语义对齐长度算起来也不会乱。如果有人习惯从 0 开始写循环也能做但很容易把区间长度 i - first 算错成 i - first 1我见过不少次这种边界错误。3.3 复杂度和内存估算这个方案的时间复杂度是 O(n)因为整个数组只扫描了一遍。哈希表的 get 和 put 在 Java 的 HashMap 实现里平均是 O(1) 的所以总耗时基本可以看成是常数级别的线性扫描。空间复杂度同样为 O(n)。最坏情况下每个前缀和都不同Map 里需要存下 n 个键值对但在这种极端情况下答案本来就是 0Map 也不会再大到哪里去整体仍然在线性范围内。这个复杂度对 OJ 题目来说非常宽裕。哪怕 n 给到一百万Java 也能轻松跑过瓶颈反而不在算法而在 Scanner 的读取效率。如果真遇到特别大的输入可以把 Scanner 换成 BufferedReader 加 StringTokenizer写法略繁琐但性能会更好。4. 提交中踩过的坑和排查方法4.1 常见的 WA 原因汇总我把自己和周围同学在这道题上常见的错误整理了一下大多集中在几个位置。第一个错误是忘记firstPos.put(0, 0)。这个问题前面已经详细说过症状是“所有从数组开头算起的合法区间都统计不到”。第二个错误是每次遇到相同前缀和时总是顺手更新 Map 里的位置firstPos.put(sum, i); // 错误示范会覆盖最早位置这样会让后续计算的最大长度越来越短。比如序列 1 0 1 0前缀和在位置 1 等于 1位置 3 也等于 1。如果第一次把 1 存为位置 1第二次 i3 时算出的长度是 3-12这没问题但如果每次都用新的位置覆盖旧的下一次再碰到 1 时基准就变成了 3而不是 1距离只会更短答案自然偏小。第三个错误是用 0 和 1 的原值做前缀和而不是转换成 -1 和 1。这种做法其实也不是完全不能做但很容易让思路变得混乱。因为直接用 0/1 计算前缀和过去的区间和是没有明确物理意义的你很难一眼看出两个前缀和相等意味着什么。不如一开始就统一转成相反数让“相等”对应“总和为 0”整个推理链条更顺。第四个错误是长度边界问题。两个前缀和相等时区间长度是i - firstPos.get(sum)不需要再加上 1。你可以理解成前缀和数组下标本身代表元素个数pre[j] 和 pre[i] 相同时中间夹的是第 j1 到第 i 个元素元素个数是 i - j。很多人习惯性写 1结果答案会比正确答案大 1碰到特定样例时就会 WA。4.2 用几个极端样例快速自测写完后不要急着交我建议先在本地敲几组数据自测。对这道题来说下面这几组是很有代表性的输入期望输出说明1\n00单个元素无法配平2\n0 12整个区间合法4\n0 0 1 14整体配对最长是全部4\n0 0 1 02中间 0 1 长度为 26\n1 1 1 0 0 06连续三个 1 再连续三个 08\n1 0 1 0 0 1 0 18交错序列整体配平如果这些样例的输出和自己想的不一致可以临时在循环里加一行调试输出打印每一步的当前位置、sum 值以及 Map 中对应 sum 的基准位置System.out.println(i i , sum sum , first firstPos.get(sum));看到实际运行轨迹后问题通常一眼就能定位。4.3 调试时的“高度可视化”技巧有一种非常直观的调试方式把前缀和画成一条折线图。遇到 1 时折线向上走一格遇到 0 时折线向下走一格。因为转换后的值是 1 和 -1所以整条折线会在某个水平高度上上下波动。题目要找的最长合法区间就是在折线上找两个高度相同且水平距离最远的点。因为从第一个高度点到第二个同高度点中间所有上升和下降完全抵消正好说明这一段里 1 和 0 的数量相等。这个视角特别适合手算小例子。比如序列 0 1 0 1你就能在纸上画出高度序列 0、-1、0、-1、0然后一眼看出两个高度 0 之间的最大距离是 4。我后来做很多前缀和题目时都习惯先画这条折线能省下不少盲目测试的时间。5. 从这道题抽象出的通用套路5.1 “最长连续子段且满足计数平衡”的统一解法“非常男女”计划虽然包装成了一个趣味题但它背后是一个非常通用的模型给定一个序列求最长连续子段使得子段满足某种计数或求和的平衡条件。这套解法的通用步骤是把题目条件转化成一个和值条件通常是“某两种数量之差为 0”或“加权和为 0”。计算前缀和核心公式是sum(l, r) pre[r] - pre[l-1]。把目标条件改写成pre[r] pre[l-1]的形式。在扫描时用哈希表记录每个前缀和第一次出现的位置相同前缀和之间夹出的区间长度就是候选答案。用ans max(ans, i - firstPos[sum])更新最长长度。这个套路能解决的不止这一道题。比如“最长和为 0 的子数组”“最长奇偶数个数相等的子数组”“能让某种前缀差值回到同一点的最长段”本质上全是同一套思路。遇到这类题第一步永远不应该是盲目枚举而是先想想条件能不能变成前缀和之间的等值或差值关系。5.2 如果要求差值不等于 0 怎么办很多人在掌握了这道题后会碰到一个变体要求 0 比 1 多 m 个或者 1 比 0 多 m 个求最长区间。这种时候条件变成了sum(l, r) m转换成前缀和就是pre[r] - pre[l-1] m也就是pre[l-1] pre[r] - m实现的时候扫描到当前前缀和 pre[r] 时不需要找与它相等的旧前缀和而是去找pre[r] - m这个值第一次出现的位置。如果存在距离就是候选答案。这个变体说明了为什么要学会灵活使用“等值前缀和”的思路而不是只会背模板。理解了pre[r] - pre[l-1]这个基本公式所有类似题目都能顺手推导出来。5.3 什么时候不能用这个套路当然不是所有区间题都能用前缀和加 Map 解决。如果题目要求的不只是“计数和相等”而是“区间内最大值最小值满足某种条件”或者“区间内所有元素互不相同”这种信息只有前缀和无法表达哈希表记录的“最早位置”也失去了意义。所以更准确地说这套方法适用于条件可以化简为前缀和之间等值或固定差值的问题。这也是为什么做题时先做数学推导很重要不要看到最长连续子数组就直接套模板。先问自己一句这个条件能不能写成关于前缀和的关系式这道题能所以它很经典。我在实际刷题中养成的习惯是拿到一个区间类问题先花两分钟在草稿纸上尝试把问题条件化为“pre[i] 与 pre[j] 的关系”如果能化出来大概率就是前缀和加哈希表的做法如果化不出来再考虑别的算法。顺便说一个从这道题里延伸出来的思想把复杂的平衡条件“编码”进数字里让最终等式变成简单形式。比如这题把 0 和 1 编码成 -1 和 1是最朴素、也最优雅的一步。生活中很多所谓“配平”“抵消”的问题归根结底都是先找到一组相反数再算累计和。我个人对这个题的体会是代码短不等于简单越短的代码越考验对模型的理解。能三分钟默写出上面那段代码并保证不踩 Map 初始化的坑说明你是真的理解了前缀和。如果现在还不能一次写对就多画几遍那条折线图等你能闭上眼把 pre[0]0 这行写出来时这道题才算真正过关。 
长河君 · 2026/10/14 12:44:58 · 阅读 1.2k 非常男女计划：前缀和+哈希表求解最长平衡子数组
前几天在OJ上刷到一道叫“非常男女”计划的老题。题目很短但不少第一次见的人会卡住给你一个长度为 n 的 0/1 序列0 和 1 分别代表两种性别要求找出最长的连续区间让区间里 0 和 1 的数量恰好相等。这道题表面是个“匹配”故事本质却是一个经典算法模型——前缀和配合哈希表求“最长连续子段和为 0”。如果你最近在练前缀和、Map 的用法或是准备笔试里常见的数组子区间问题很值得把它吃透。我最早做这道题时也绕了一段弯路第一反应写了个 O(n^2) 的前缀和暴力结果数据一大直接超时。后来把思路换成“记录前缀和第一次出现的位置”代码很短跑起来却非常稳。这篇就把完整思路、Java 实现、以及我踩过的坑一次性说清楚。1. 先弄明白题目在找什么1.1 把“男女配平”翻译成数学条件题目里的连续区间可以理解成“在一条队伍中随便截取连续的一段”。假设这一段里有 x 个 0y 个 1题目要求的是 x y。这个条件看似简单但处理起来有个隐蔽的难点0 和 1 是两种离散状态你没办法像做一般的子数组求和那样直接套用“当前区间和等于某个目标值”的模板。很多人第一反应是暴力枚举所有的左端点和右端点然后统计中间 0 和 1 的个数复杂度 O(n^3)显然不可取稍微优化一点先用前缀和预处理出 0 的数量和 1 的数量再枚举左右端点复杂度降到 O(n^2)但 n 一旦到了十万级别依然会超时。所以必须换思路。关键点在于x y 这个条件等价于“x - y 0”。如果我们能给每个数字重新赋一个权重让 0 和 1 的贡献相反那么“两种数量相等”就变成了“区间内权重和为 0”。这可比分别统计两种数量优雅得多。我一般习惯这样定义遇到 0 记作 -1遇到 1 记作 1。当然反过来也行具体哪个对应男生、哪个对应女生不重要重要的是让两种值在求和时互相抵消。只要这两个值互为相反数问题性质就完全一样。1.2 为什么滑动窗口在这里不灵很多同学看到“连续子段”“最长”这两个词第一反应就是滑动窗口。我开始也这么想过但很快发现这题不能用双指针。原因在于滑动窗口正常运行的前提是“单调性”窗口变大或缩小时我们关心的指标要能判断出该不该收缩左边界。比如求最长无重复字符的子串右指针往前走遇到重复字符时窗口一定不合法必须收缩左边界直到合法这个过程是确定的。但这道题里你没办法判断右指针往前移动后左指针到底该不该动。举个例子。假设当前窗口 [left, right] 里 0 的数量比 1 多 2 个右指针继续往右走如果遇到一个 1差值会变成 1窗口变得更接近合法这时候你如果按“不合法就收缩左边界”的逻辑去处理反而可能丢掉一个更长的合法区间。反过来一个已经合法的窗口右指针加一个 0 进来差值变成 -1又变得不合法了但你无法保证后面再加几个 1 会不会再次平衡。也就是说差值变化是双向的窗口扩大不一定让条件更差窗口缩小也不一定让条件更好。这种情况下双指针就没有单调性可言强行滑动窗口会漏掉正确答案。所以这道题必须放弃“用指针维护一个当前窗口”的直觉转而用前缀和来做。2. 核心思路把问题变成“前缀和出现相同值”2.1 重新编码让 0 和 1 变成相反数先把输入的每个数字做一次映射0 变成 -11 变成 1。例如序列0 1 0 0 1 1转换后就是-1 1 -1 -1 1 1这样做的好处是任意一个区间内如果 0 和 1 数量相等那么转换后的数字相加必然为 0。因为假设区间里有 a 个 0、a 个 1那么区间总和就是 a×(-1) a×(1) 0反过来如果区间总和是 0设 0 的个数为 x1 的个数为 y则总和是 -x y等于 0 时只能推出 x y。所以这道题等价于在转换后的数组中找一个最长的连续子数组使得子数组的和为 0。这个等价关系一旦建立问题就清爽了许多。接下来需要解决的就是一个很经典的子问题怎么高效判断并找出“和为 0 的最长连续子数组”。2.2 区间和如何用前缀和表示为了快速计算任意区间的和我们引入前缀和数组 pre。定义方式如下pre[0] 0表示前 0 个元素的和pre[i] pre[i-1] 转换后的第 i 个元素其中 i 从 1 开始。于是数组 pre[i] 表示“前 i 个元素转换后的总和”。任何一个区间 [l, r] 的和都可以用两个前缀和做减法得到sum(l, r) pre[r] - pre[l-1]如果要求某个区间和为 0也就是pre[r] - pre[l-1] 0化简就是pre[r] pre[l-1]这句话才是整道题的核心如果在前缀和数组中两个位置的值相等那么这两个位置之间的原始区间0 和 1 的数量一定相等。不信可以拿一个简单例子试。假设原序列是0 1 0 1转换后是-1 1 -1 1前缀和依次是pre[0] 0pre[1] -1pre[2] 0pre[3] -1pre[4] 0注意 pre[0]、pre[2]、pre[4] 都等于 0。pre[0] 到 pre[2] 之间夹的是前两个元素即 0 1中间正好一男一女合法pre[0] 到 pre[4] 之间是全部四个元素0 1 0 1也合法长度是 4。pre[2] 到 pre[4] 之间是后两个元素 0 1同样合法。再比如 pre[1] 和 pre[3] 都等于 -1它们之间夹的是第 2 到第 3 个元素也就是 1 0也合法。所以现在问题被彻底改写了我们要在所有满足 pre[i] pre[j] 的 i j 中找 j - i 最大的那一对。这个最大差值就是答案。2.3 用 Map 记录“第一次出现的位置”既然要最大化 j - i那么当我们要比较前缀和相同的两个位置时自然希望 i 越小越好、j 越大越好。我们可以从左到右扫描一遍原始数组同时维护当前前缀和 sum。每到一个新位置 i就看一下当前 sum 在之前是否出现过如果出现过说明从“第一次出现的位置”到现在的 i 这一段是合法的长度 i - firstPosition如果没出现过就把当前 sum 和当前位置记录进哈希表注意这个位置将成为未来所有相同 sum 的比较基准。这里最关键的细节是哈希表里存的一定是“最早出现的位置”而不是最近出现的位置。因为两个相同前缀和之间夹出来的区间都是合法区间我们要的是最长距离用最早位置去减才能得到最大长度。还是上面的例子遇到 pre[4] 0 时哈希表里 0 最早出现在位置 0所以算出长度 4 - 0 4正好是整段序列最长合法区间。如果错误地把位置 2 当成 0 的基准算出来就只有 4 - 2 2答案就会偏小。另外要注意前缀和完全可能是负数尤其是把 0 变成 -1 之后前缀和会在负数区间频繁出现。用 Java 的 HashMap 来存键值对就不用担心负数下标问题这是比直接用数组做偏移量更省心的地方。3. Java 代码怎么写才不容易错3.1 完整可提交的代码把上面的思路落成 Java 代码核心逻辑其实只有十来行。完整版本如下import java.util.HashMap; import java.util.Map; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); MapInteger, Integer firstPos new HashMap(); // 空前缀和 0 的下标是 0必须初始化 firstPos.put(0, 0); int sum 0; int ans 0; for (int i 1; i n; i) { int x sc.nextInt(); // 0 看成 -11 看成 1 sum (x 1 ? 1 : -1); if (firstPos.containsKey(sum)) { ans Math.max(ans, i - firstPos.get(sum)); } else { firstPos.put(sum, i); } } sc.close(); System.out.println(ans); } }一个常见的写法是把数组先存下来再跑第二遍循环。但这题其实完全不用存原始数组因为边读边算已经足够。这样既省内存代码也更紧凑。提交时记得类名必须是 Main不要带 package 声明在大多数 OJ 上用 Scanner 读十万级数据完全没问题不需要额外引入更复杂的快速输入类。3.2 初始化与边界处理代码里最容易被忽略的一行就是firstPos.put(0, 0)。如果不放这一行那么当前缀和首次回到 0 时你是找不到基准位置的。举例来说序列只有两个数1 0转换后是 1 -1前缀和是 pre[0]0、pre[1]1、pre[2]0。正确结果应该是 2因为整个区间里 1 和 0 数量相等。计算过程是扫描到 i2 时 sum0此时能够在 Map 里查到 0 的第一次位置是 0于是 ans2-02。如果没初始化Map 里没有 0 这个键sum0 会被当成第一次出现最终答案变成 0直接 WA。另一个边界是如果整个序列无论如何都无法配平比如全 0 或者全 1那么最终答案就是 0。代码里 ans 的初始值是 0这种情况下自然输出 0不需要额外特判。循环里的下标也建议从一开始写一直写到 n因为前缀和 pre[i] 表示前 i 个元素。这样和“位置 0 代表空前缀”的语义对齐长度算起来也不会乱。如果有人习惯从 0 开始写循环也能做但很容易把区间长度 i - first 算错成 i - first 1我见过不少次这种边界错误。3.3 复杂度和内存估算这个方案的时间复杂度是 O(n)因为整个数组只扫描了一遍。哈希表的 get 和 put 在 Java 的 HashMap 实现里平均是 O(1) 的所以总耗时基本可以看成是常数级别的线性扫描。空间复杂度同样为 O(n)。最坏情况下每个前缀和都不同Map 里需要存下 n 个键值对但在这种极端情况下答案本来就是 0Map 也不会再大到哪里去整体仍然在线性范围内。这个复杂度对 OJ 题目来说非常宽裕。哪怕 n 给到一百万Java 也能轻松跑过瓶颈反而不在算法而在 Scanner 的读取效率。如果真遇到特别大的输入可以把 Scanner 换成 BufferedReader 加 StringTokenizer写法略繁琐但性能会更好。4. 提交中踩过的坑和排查方法4.1 常见的 WA 原因汇总我把自己和周围同学在这道题上常见的错误整理了一下大多集中在几个位置。第一个错误是忘记firstPos.put(0, 0)。这个问题前面已经详细说过症状是“所有从数组开头算起的合法区间都统计不到”。第二个错误是每次遇到相同前缀和时总是顺手更新 Map 里的位置firstPos.put(sum, i); // 错误示范会覆盖最早位置这样会让后续计算的最大长度越来越短。比如序列 1 0 1 0前缀和在位置 1 等于 1位置 3 也等于 1。如果第一次把 1 存为位置 1第二次 i3 时算出的长度是 3-12这没问题但如果每次都用新的位置覆盖旧的下一次再碰到 1 时基准就变成了 3而不是 1距离只会更短答案自然偏小。第三个错误是用 0 和 1 的原值做前缀和而不是转换成 -1 和 1。这种做法其实也不是完全不能做但很容易让思路变得混乱。因为直接用 0/1 计算前缀和过去的区间和是没有明确物理意义的你很难一眼看出两个前缀和相等意味着什么。不如一开始就统一转成相反数让“相等”对应“总和为 0”整个推理链条更顺。第四个错误是长度边界问题。两个前缀和相等时区间长度是i - firstPos.get(sum)不需要再加上 1。你可以理解成前缀和数组下标本身代表元素个数pre[j] 和 pre[i] 相同时中间夹的是第 j1 到第 i 个元素元素个数是 i - j。很多人习惯性写 1结果答案会比正确答案大 1碰到特定样例时就会 WA。4.2 用几个极端样例快速自测写完后不要急着交我建议先在本地敲几组数据自测。对这道题来说下面这几组是很有代表性的输入期望输出说明1\n00单个元素无法配平2\n0 12整个区间合法4\n0 0 1 14整体配对最长是全部4\n0 0 1 02中间 0 1 长度为 26\n1 1 1 0 0 06连续三个 1 再连续三个 08\n1 0 1 0 0 1 0 18交错序列整体配平如果这些样例的输出和自己想的不一致可以临时在循环里加一行调试输出打印每一步的当前位置、sum 值以及 Map 中对应 sum 的基准位置System.out.println(i i , sum sum , first firstPos.get(sum));看到实际运行轨迹后问题通常一眼就能定位。4.3 调试时的“高度可视化”技巧有一种非常直观的调试方式把前缀和画成一条折线图。遇到 1 时折线向上走一格遇到 0 时折线向下走一格。因为转换后的值是 1 和 -1所以整条折线会在某个水平高度上上下波动。题目要找的最长合法区间就是在折线上找两个高度相同且水平距离最远的点。因为从第一个高度点到第二个同高度点中间所有上升和下降完全抵消正好说明这一段里 1 和 0 的数量相等。这个视角特别适合手算小例子。比如序列 0 1 0 1你就能在纸上画出高度序列 0、-1、0、-1、0然后一眼看出两个高度 0 之间的最大距离是 4。我后来做很多前缀和题目时都习惯先画这条折线能省下不少盲目测试的时间。5. 从这道题抽象出的通用套路5.1 “最长连续子段且满足计数平衡”的统一解法“非常男女”计划虽然包装成了一个趣味题但它背后是一个非常通用的模型给定一个序列求最长连续子段使得子段满足某种计数或求和的平衡条件。这套解法的通用步骤是把题目条件转化成一个和值条件通常是“某两种数量之差为 0”或“加权和为 0”。计算前缀和核心公式是sum(l, r) pre[r] - pre[l-1]。把目标条件改写成pre[r] pre[l-1]的形式。在扫描时用哈希表记录每个前缀和第一次出现的位置相同前缀和之间夹出的区间长度就是候选答案。用ans max(ans, i - firstPos[sum])更新最长长度。这个套路能解决的不止这一道题。比如“最长和为 0 的子数组”“最长奇偶数个数相等的子数组”“能让某种前缀差值回到同一点的最长段”本质上全是同一套思路。遇到这类题第一步永远不应该是盲目枚举而是先想想条件能不能变成前缀和之间的等值或差值关系。5.2 如果要求差值不等于 0 怎么办很多人在掌握了这道题后会碰到一个变体要求 0 比 1 多 m 个或者 1 比 0 多 m 个求最长区间。这种时候条件变成了sum(l, r) m转换成前缀和就是pre[r] - pre[l-1] m也就是pre[l-1] pre[r] - m实现的时候扫描到当前前缀和 pre[r] 时不需要找与它相等的旧前缀和而是去找pre[r] - m这个值第一次出现的位置。如果存在距离就是候选答案。这个变体说明了为什么要学会灵活使用“等值前缀和”的思路而不是只会背模板。理解了pre[r] - pre[l-1]这个基本公式所有类似题目都能顺手推导出来。5.3 什么时候不能用这个套路当然不是所有区间题都能用前缀和加 Map 解决。如果题目要求的不只是“计数和相等”而是“区间内最大值最小值满足某种条件”或者“区间内所有元素互不相同”这种信息只有前缀和无法表达哈希表记录的“最早位置”也失去了意义。所以更准确地说这套方法适用于条件可以化简为前缀和之间等值或固定差值的问题。这也是为什么做题时先做数学推导很重要不要看到最长连续子数组就直接套模板。先问自己一句这个条件能不能写成关于前缀和的关系式这道题能所以它很经典。我在实际刷题中养成的习惯是拿到一个区间类问题先花两分钟在草稿纸上尝试把问题条件化为“pre[i] 与 pre[j] 的关系”如果能化出来大概率就是前缀和加哈希表的做法如果化不出来再考虑别的算法。顺便说一个从这道题里延伸出来的思想把复杂的平衡条件“编码”进数字里让最终等式变成简单形式。比如这题把 0 和 1 编码成 -1 和 1是最朴素、也最优雅的一步。生活中很多所谓“配平”“抵消”的问题归根结底都是先找到一组相反数再算累计和。我个人对这个题的体会是代码短不等于简单越短的代码越考验对模型的理解。能三分钟默写出上面那段代码并保证不踩 Map 初始化的坑说明你是真的理解了前缀和。如果现在还不能一次写对就多画几遍那条折线图等你能闭上眼把 pre[0]0 这行写出来时这道题才算真正过关。