洛谷P1114这道“非常男女”计划我第一次读题时还以为是道关于配对的模拟题点进去才发现它是一道很经典的前缀和练手题在各大OJ和算法入门清单里都常驻。题目本身不复杂但能从一个“统计男女数量相等的最长连续区间”的问题里引出前缀和、哈希映射、数组下标偏移这一整套基础功非常适合刚学完数组和基础数据结构、准备迈入算法刷题阶段的Java同学。这篇文章我就从题意拆解、核心思路一步步讲到最终代码和踩坑记录把这道题完整讲透。1. 题意拆解这道题到底在求什么1.1 读懂“非常男女”的隐藏要求题目给定一个长度为n的序列序列里每个位置只可能是两个值一般是0和1用来表示女生和男生。题目要求找出一段连续的子区间使得这个区间里0和1的数量一样多而且这个区间的长度要尽可能长最后输出最长的长度。这里有几个容易忽略的关键信息必须是连续的一段不是让你随便从序列里挑若干个位置出来拼凑。题目光看输入输出样例很容易误以为只要找“相邻的一对男女”就行实际上最少可以是一男一女挨在一起但也可能是几千个位置组成的大区间。输出的是长度不是起止位置更不是方案数。举个例子如果序列是1 1 1 0 0 0男生有三个、女生有三个而且刚好排在一起那么整个序列本身就是男女数量相等的区间长度是6。但如果序列是1 0 0 1 1你要自己找一找最长的平衡区间在哪一段可能是中间的1 0 0 1也可能是某两个相邻位置这就要靠算法来统一处理了。1.2 朴素思路为什么不能直接写看到这种“找区间”的题很多人的第一反应和我一样枚举所有左端点和右端点然后统计区间里0和1的个数判断是否相等记录最大长度。这种暴力做法的时间复杂度是O(n^2)甚至O(n^3)。如果n比较小比如几百那完全没问题但这类题的数据范围通常会把n推到10^5这个量级O(n^2)意味着最多要执行约10^10次操作Java在默认评测环境下根本无法在时限内跑完。换成更直观的说法想象有100000个人站成一排你要检查所有可能的“从第i个到第j个”这些人之间的男女差。每两个人之间都要统计一遍就算每个人都身怀绝技这个统计量也太大。所以必须换一种眼光把“一段人”的信息压缩成某个能快速比较的状态这正是前缀和能发挥作用的地方。2. 核心思路把性别变成数字问题立刻变简单2.1 为什么男生记1、女生记-1前缀和的核心操作是把一个序列的累积信息存下来。这里的关键技巧是把题目中的0和1映射成1和-1。男生记为1对前缀和的贡献是 1女生记为0对前缀和的贡献是 -1用变量sum记录“当前位置之前所有人贡献的总和”。当sum的数值在某两个位置相等时说明这两个位置之间的那段1和-1的数量恰好抵消了也就是男生数量等于女生数量。这个思路的本质是区间内男女数量相等等价于区间内所有值的和为0。既然要求一段区间的和为0自然就想到用前缀和来判断。前缀和数组pre[i]表示前i个元素的累加和那么区间[l, r]的和就是pre[r] - pre[l-1]。要让这个差值为0只需要pre[r] pre[l-1]。所以问题就变成了在所有前缀和相等的位置对(i, j)中找出j - i的最大值。2.2 前缀和相同意味着什么先看一个具体例子输入1 1 1 0 0 0映射后就是1 1 1 -1 -1 -1。我手动算一遍前缀和前1个sum 1前2个sum 2前3个sum 3前4个sum 2前5个sum 1前6个sum 0注意看前缀和为2出现在位置2和位置4前缀和为1出现在位置1和位置5前缀和为0出现在初始位置位置0和位置6。那么位置2到位置4这一段[1, -1]的和是0长度2位置1到位置5这一段[1, 1, -1, -1]的和是0长度4位置0到位置6更是整个序列长度6。答案取最大就是6。这个“位置0”非常关键。很多人第一次写的时候容易忽略初始状态一个元素都还没取的时候前缀和就是0。如果漏掉它那么像整段序列本身就平衡的情况就永远统计不到因为找不到和0相等的另一个前缀和位置。后面写代码时必须把这个初始状态显式记录进去。2.3 记录“最早出现位置”还是“哈希表”现在目标明确遍历一遍序列不断更新前缀和sum然后判断这个sum之前有没有出现过。如果出现过假设之前最早出现的位置是first那么当前位置i到first 1这一段就是平衡区间长度是i - first如果没出现过就把当前sum和当前位置i存下来。这里有个细节应该存“最早出现的位置”而不是“最近出现的位置”。因为我们要的是最长区间一旦某个前缀和多处出现那么最早出现的位置和最晚出现的位置之间肯定跨度最大。所以记录最早位置就够用了之后遇到同一个sum只需要用当前位置减去最早位置。数据结构方面有两种主流选择用HashMapInteger, Integer键是前缀和值是最早出现的位置。用一个整数数组因为sum的取值范围是[-n, n]总共2n 1种可能直接开一个大小为2n 1的数组加上偏移量来映射下标。两种方式都能通过但在Java里HashMap会涉及自动装箱、哈希计算和扩容常数比较大数组直接按下标访问速度更稳。这道题n最多10^5HashMap其实也能过但如果养成了“能用数组就不上哈希表”的习惯对后续处理更大数据范围的题目会很有帮助。下面我会把两种版本都写出来并说明为什么最终选择数组。3. Java实现从第一版到最终版3.1 第一版用HashMap的直白写法先给出最符合思维逻辑的版本。这个版本把所有状态都放进了Map里读起来非常直观适合用来理解算法本身。import java.util.HashMap; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc new Scanner(System.in); int n sc.nextInt(); HashMapInteger, Integer first new HashMap(); first.put(0, 0); int sum 0; int ans 0; for (int i 1; i n; i) { int x sc.nextInt(); sum (x 1 ? 1 : -1); if (first.containsKey(sum)) { ans Math.max(ans, i - first.get(sum)); } else { first.put(sum, i); } } System.out.println(ans); } }这段代码的逻辑就是核心思路的直接翻译first.put(0, 0)表示在位置0前缀和为0已经出现过。每次读一个数按性别把sum加1或减1。如果当前sum之前在first里出现过就拿当前位置减最早位置更新答案。如果没出现过就把当前位置存成这个sum的最早位置。这里有个容易想错的地方为什么更新完答案后不把当前sum的位置也更新成i因为我们要的是最长区间如果用i覆盖掉最早位置那么后续再遇到同一个sum时计算出来的长度只会更短就永远失去了潜在的最优解。所以只在第一次出现时记录位置之后一律只用来算长度。3.2 最终版用数组映射代替哈希表理解了HashMap版本之后再来写出竞赛里更推荐的数组版本。虽然代码稍微长一点但其实只是多了一个下标偏移的处理。import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.Arrays; public class Main { public static void main(String[] args) throws IOException { BufferedReader br new BufferedReader(new InputStreamReader(System.in)); int n Integer.parseInt(br.readLine()); int[] first new int[2 * n 1]; Arrays.fill(first, -1); int offset n; first[offset] 0; int sum 0; int ans 0; String[] parts br.readLine().split( ); for (int i 1; i n; i) { int x Integer.parseInt(parts[i - 1]); sum (x 1 ? 1 : -1); int idx sum offset; if (first[idx] -1) { first[idx] i; } else { ans Math.max(ans, i - first[idx]); } } System.out.println(ans); } }这里最核心的映射关系是前缀和sum的范围是[-n, n]所以我把sum加上偏移量n得到[0, 2n]范围的下标正好对应数组first的长度2n 1。举个例子sum 0对应下标nfirst[n] 0就是初始状态。sum 3对应下标n 3。sum -2对应下标n - 2。数组first的每个元素一开始都是-1代表这个前缀和还没有出现过。一旦遇到某个前缀和第一次出现就把当前位置写进去。之后如果又遇到同一个前缀和就说明这一段区间男女平衡更新答案。3.3 提交前的几个检查点每次写完代码准备提交时我习惯快速过一遍这些细节这道题的坑基本都集中在这里first数组的长度必须是2 * n 1因为最极端情况下前n个全是男生sum能到n前n个全是女生sum能到-n。总共n - (-n) 1 2n 1个状态。first[offset]必须初始化成0这个offset就是n对应前缀和0。如果不初始化整段序列平衡的情况就会漏掉。我实测中确实见过不少人卡在这个点上样例能过但提交后某个测试点答案少了一截。数组默认值不能直接用0因为位置0已经被占用了如果用0表示“未出现”那么初始状态sum0的位置也是0会混淆。所以统一用-1表示未出现用Arrays.fill(first, -1)初始化。输入读取这道题n最多10^5第二行数据量不大用BufferedReader加split完全够用。如果后续遇到更大数据范围可以改成StreamTokenizer或自定义快速输入但这里没必要。类名必须是Main在洛谷这类OJ平台提交Java代码时主类名通常必须叫Main否则编译阶段就报错。这个细节看起来不起眼实际提交时却很容易翻车。4. 复杂度分析与边界情况4.1 时间复杂度和空间复杂度整个算法的核心循环只有一次for循环从位置1遍历到位置n每次操作都是O(1)更新sum一次加法。计算数组下标一次加法。判断数组值并更新答案一次比较和一次赋值。所以时间复杂度是O(n)无论n多大只要数据读取跟得上遍历一遍就能出答案。空间上只用了一个长度2n 1的数组也是O(n)。对比暴力解法的O(n^2)甚至O(n^3)这个效率提升是很明显的。如果把n看作10^5暴力可能需要执行上亿次操作而前缀和方案只需要执行约10万次核心操作速度差了好几个数量级。4.2 边界条件最容易踩的坑这类题目的边界条件经常藏在一些“看起来不用管”的地方。第一个边界是n 1。序列只有一个位置无论它是男是女都不可能形成平衡区间答案应该是0。在代码中sum第一次变到1或-1对应的数组下标位置是-1所以只记录不更新答案最终ans保持0。这个行为是自然的。第二个边界是序列本身从第一个位置开始就连续平衡。比如1 0 1 0 1 0最长的平衡区间就是整个序列长度6。这时候必须保证first[n] 0这条初始状态生效。我手动跑一遍这个输入i1x1sum1first[n1]1i2x0sum0idxnfirst[n]不为-1ans2-02i3x1sum1idxn1first存在ans3-12i4x0sum0idxnans4-04i5sum1idxn1ans5-14i6sum0idxnans6-06遍历完答案是6。第三个边界是序列里全是同一种性别。比如1 1 1 1前缀和是1、2、3、4没有任何重复答案保持0。如果全是0 0 0 0前缀和是-1、-2、-3、-4同样没有重复答案也是0。这说明代码不会因为负数下标而崩溃因为偏移量offset已经把-4映射到n-4这个合法位置了。4.3 为什么更新答案的时机不能反过来我见过不少初写者在else分支里也写ans Math.max(ans, i - first[idx])这样看起来也没错但要注意既然进了else分支就说明之前这个前缀和出现过计算出来的i - first[idx]一定是个有意义的候选答案。真正容易出问题的是把逻辑写成if (first[idx] -1) { first[idx] i; ans Math.max(ans, i - first[idx]); }这样写就错误了。因为当某个前缀和第一次出现时first[idx]刚被设置成ii - first[idx]恒等于0永远不会产生正确答案而且还会把第一次出现的状态错误地当成一种合法区间。这个错误比较隐蔽因为程序不会报错只是答案一直偏小。判断“该不该更新答案”的标准其实只有一个当前前缀和是否之前已经出现过。如果出现过才有可能形成非空区间如果从没出现过就不可能凭空形成区间。所以答案更新只能放在“已存在”的分支里。5. 常见卡壳点排查与优化心得5.1 我实测中遇到的三个问题这道题我前后给几位同学讲过他们实际写代码时遇到的问题还挺有代表性我在这里整理一下。第一个问题是first数组初始化用了0而不是-1。表面上看数组默认就是0省去Arrays.fill这一步很省事。但问题在于first[n] 0这个初始状态和“未出现”的标志冲突了。一旦遇到sum0的情况程序不知道这是初始状态还是某个未记录的非法状态或者更严重地当某个前缀和对应的下标恰好是数组默认值0的位置会被误判成“已经出现过”导致计算出错误答案。所以只要用数组记录状态最好统一默认值并用一个不可能出现的值表示“未出现”在本题里-1是最合适的因为位置索引从0开始任何真实位置都不可能是负数。第二个问题是边界读取问题。有人用Scanner一行一行读结果第二行数据可能跨多行nextInt()本身没问题但如果用readLine()处理就需要小心第二行是否存在换行或者空串。我在文章最终版里用的是br.readLine().split( )默认假设所有数据在同一行。如果题目输入格式不保证这一点更稳妥的方式是直接用Scanner或者StringTokenizer循环读取每个整数避免跨行问题。这道题的输入一般是一行但养成用StringTokenizer的习惯能稳妥处理各种空白字符。第三个问题是对“偏移量”不够理解。有的同学会写成int idx sum n 1理由是怕sum n越界。实际上sum的最小值是-n加上n得到0最大值是n加上n得到2n。数组下标范围是0到2nsum n正好覆盖这个范围不需要再加1。如果多加了1数组末尾空出一个位置虽然不影响正确性但说明没有真正搞懂映射关系。写代码之前最好在纸上画一条数轴标出-n到n和0到2n的对应关系。5.2 前缀和状态压缩的通用套路做完这道题值得再往深想一层这种“把区间和转化为前缀和相等”的思路并不仅仅适用于男女配对问题。比如题目换成“求最长的一段其中1比0多k个”那么条件就变成pre[r] - pre[l-1] k也就是pre[r] - k pre[l-1]。在遍历时除了记录当前前缀和最早出现位置还需要额外查询sum - k这个值是否出现过。逻辑完全一致只是判断条件多了一个偏移。再比如“求最长的一段使得子段和对某个数取模后等于0”那就是记录前缀和取模后的值遇到同样的余数就形成候选区间。这些都是同一个套路的变体。如果把“男生1女生-1”这个技巧再延伸还可以处理“只有两类对象、要求数量差为固定值”的问题。背后的本质是当区间合法性只和区间内两类元素的数量差有关时就可以利用前缀和把区间问题转化为两个独立位置之间的关系再用哈希表或数组把O(n^2)降为O(n)。5.3 关于Java输入输出优化的补充洛谷这类在线评测平台对Java的时间限制通常比C宽松一些但也不是无限宽松。这道题数据范围10^5用Scanner完全没问题但如果你准备长期刷题建议从一开始就习惯使用BufferedReader和BufferedWriter。原因很简单Scanner在每次读取时做大量格式解析和缓冲区操作数据量一大就会成为性能瓶颈而BufferedReader按行读取字符串再手动解析整数性能稳定得多。附带提一下输出如果题目要求输出多行结果用StringBuilder拼接后一次性输出比每次System.out.println快非常多。本题只输出一个整数直接println就好。结尾这道“非常男女”计划做完之后我最大的感受是很多看似需要枚举区间的题目一旦想到“用相反数表示两类对象”和“记录前缀和最早出现位置”这两招复杂度就能瞬间降下来。后来遇到好几个和配对、差值、余数相关的算法题我都会下意识地想能不能把问题转换成前缀和相等或前缀和差固定的形式。这个思维习惯带来的收益远不止P1114这一道题。最后再分享一个实战中的小建议第一次写这道题时不要急着看题解先在草稿纸上手动模拟几组小数据。比如自己写一个1 0 1 0画出前缀和的变化过程标出每个sum第一次出现的位置你会比我讲任何理论都更直观地理解为什么first[n] 0不能丢为什么答案要更新在“已存在”的分支里。把这些手感练出来了以后再遇到前缀和的题你就能少走很多弯路。