如果你刷LeetCode刷到第525题大概率已经见过它的大名Contiguous Array中文一般叫“连续数组”。这道题在热门100题里长期占着一个位置但很多人第一次看会有点懵给一个只含0和1的数组找到含有相同数量0和1的最长连续子数组并返回长度。乍一听像是滑动窗口或者双指针结果真去写滑动窗口的时候会发现窗口的收缩条件根本没法定义。真正上手之后才发现这道题考的是前缀和加哈希表那个经典套路——把0当成-1让问题变成找和为0的最长子数组。这篇文章不是单纯贴个题解而是把525背后的知识点、推导过程、同类题和坑位一次讲清楚适合正在刷热门100题、准备面试或者想系统整理“前缀和”这一类题型的读者。1. 连续数组这道题凭什么值得单独做一次知识点总结1.1 题目原貌一个看似简单的统计问题先把原题翻译成人话。给你一个二进制数组nums也就是数组里只可能有0和1两种值。要求找一个连续子数组使得这个子数组里0的数量和1的数量相等返回所有满足条件的子数组里长度最长的那一个的长度。举个例子输入: [0,1] 输出: 2因为整个数组里1个0、1个1长度就是2。再看一个输入: [0,1,0] 输出: 2这里最长的平衡子数组是[0,1]或[1,0]长度都是2。注意不能把整个数组算进去因为整个数组是2个0、1个1不相等。再看一个复杂点的输入: [0,0,1,0,0,0,1,1] 输出: 6答案是[0,0,1,0,0,0,1,1]中间的一段我们数一下下标1到6是[0,1,0,0,0,1]里面3个0、3个1长度为6。或者下标0到5是[0,0,1,0,0,0]里面4个0、2个1不行。所以答案是6。题目本身不长但难点在于怎么高效地找到这个最长长度。数组长度最高能到10^5级别如果你真去枚举所有子数组那复杂度就是O(n^2)面试官绝对会摇头。1.2 从“数0和1”到“前缀和归零”的转换这道题最巧妙的点在于不要真的去数0和1的个数。我们可以做一个替换把数组里的0看成-1把1看成1。这样一替换原来的数组就变成了一个由1和-1组成的新数组。那么这个新数组的任意一个连续子数组的“和”是什么意思如果某个子数组里0和1数量相等那么在这个替换后的数组里这个子数组的和一定是0。反过来如果替换后的某个子数组和为0那么它里面1和-1的个数一定相等也就是原数组里1和0的个数相等。这就把问题从“统计相等”变成了“求区间和为0的最长区间”。而区间和问题正好是前缀和的专长。我把这个转化单独拿出来说是因为很多朋友刷这道题时卡住不是卡在代码而是卡在“为什么要把0看成-1”。你想如果0和1要数量相等那就是“1的个数 - 0的个数 0”。所以每个0贡献 -1每个1贡献 1正好用差值来度量平衡。1.3 暴力法的复杂度瓶颈在没有前缀和思想之前最容易想到的暴力做法是枚举所有子数组的左端点i。枚举所有子数组的右端点j。统计nums[i..j]里0和1的个数判断是否相等更新答案。这么做的时间复杂度是O(n^3)因为枚举左右端点已经是O(n^2)再统计0和1的个数又要扫一遍区间。就算用前缀和数组先预处理把统计个数优化成O(1)整体也还是O(n^2)。当n 10^5时O(n^2)意味着10^10量级的操作超时是必然的。这也就是为什么不能用滑动窗口直接硬做滑动窗口通常依赖单调性而“0和1数量相等”这个条件在窗口扩张和收缩时并不单调窗口大了可能平衡窗口小了也可能平衡很难找到一个明确的收缩规则。暴力不行滑动窗口不行那就只能从“区间和”这个角度切入用前缀和。2. 前缀和与哈希表从数学推导到接口设计2.1 前缀和数组的朴素写法先回忆一下前缀和的定义。对于一个数组a定义pre[0] 0 pre[i] a[0] a[1] ... a[i-1]也就是说pre[i]表示原数组前i个元素的和。那么任意区间[j, i)的和就可以写成sum(a[j..i-1]) pre[i] - pre[j]对于这道题我们把nums里的0替换成-1然后构造前缀和。如果pre[i] pre[j]就说明区间[j, i)的和为0也就是原数组中0和1的数量相等。最朴素的做法是先构造完整的前缀和数组然后用两层循环找所有pre[i] pre[j]的对计算i - j的最大值。这仍然是O(n^2)因为我们把乘积级的时间花在了“找相同前缀和”这个环节。那有没有办法在一次遍历中同时记录前缀和并且快速找到“这个前缀和之前是否出现过”有用哈希表。2.2 为什么哈希表只记录“最早出现的下标”哈希表的 key 是前缀和的值value 是这个前缀和值第一次出现时的下标或者更准确地说是遍历过程中最早出现的位置。为什么只记录最早出现的位置而不是把所有出现位置都存下来因为我们要求的是最长子数组。对于同一个前缀和值假设它出现在下标pos1和pos2且pos1 pos2。那么以当前下标i为右端点时能形成的平衡子数组长度是i - pos。为了让长度更长pos当然越小越好。所以只要记录这个前缀和值第一次出现的位置就够了。如果题目改成“求最短的平衡子数组”那反而要记录最新出现的位置。这也是一类题目的常见变形。2.3 长度公式i - first[sum]的完整推导假设我们已经处理到原数组下标i从0开始当前维护的前缀和是cur。如果cur之前出现过最早出现位置是first[cur]那么代表从first[cur] 1到i这一段的和为pre[i1] - pre[first[cur]1] cur - cur 0这段的长度是i - (first[cur] 1) 1 i - first[cur]所以代码里的更新就是ans max(ans, i - first[cur])这里有个关键细节first[0]必须初始化为-1。为什么因为前缀和的初始值0出现在数组开头之前我们可以把它看成是“空前缀”的位置-1。不初始化-1的话当整个数组的前缀和再次变成0时比如原数组就是[0,1]你会漏掉从开头到当前下标这一段长度为2的答案。我们来手动跑一下[0,1]的流程感受这个公式初始化哈希表first里面放{0: -1}cur 0ans 0。i 0nums[0] 0所以cur -1cur -1。-1不在哈希表里记录first[-1] 0。i 1nums[1] 1所以cur 1cur 0。0在哈希表里最早位置是-1长度 1 - (-1) 2更新ans 2。正确。再看一个[0,1,0]i0cur-1存first[-1]0。i1cur0哈希表里有0:-1长度1-(-1)2ans2。注意这里不需要更新first[0]因为我们要保留最早位置。i2cur-1哈希表里有-1:0长度2-02ans保持2。最终答案2正确。2.4 一次遍历的代码实现C / PythonC 实现class Solution { public: int findMaxLength(vectorint nums) { unordered_mapint, int first; first[0] -1; int cur 0, ans 0; for (int i 0; i nums.size(); i) { cur nums[i] 1 ? 1 : -1; if (first.count(cur)) { ans max(ans, i - first[cur]); } else { first[cur] i; } } return ans; } };Python 实现class Solution: def findMaxLength(self, nums: List[int]) - int: first {0: -1} cur 0 ans 0 for i, x in enumerate(nums): cur 1 if x 1 else -1 if cur in first: ans max(ans, i - first[cur]) else: first[cur] i return ans注意 C 里first.count(cur)用来判断是否存在Python 里用cur in first。不要用first[cur]直接判断否则不存在的 key 会被默认插入这个坑后文会细讲。复杂度分析时间复杂度O(n)每个元素只遍历一次哈希表操作均摊O(1)。空间复杂度O(n)前缀和值最多有2n1种哈希表大小和n线性相关。3. 这类题型的通用套路把条件转换成可比较的数值3.1 通用套路替换 前缀和 哈希表刷到525之后你会发现它其实代表了一整套题型。这类题的核心套路可以总结成三步第一步替换。把题目里“A和B数量相等”或者“某种差值为某个目标”的条件转换成数值形式。最常见的就是把一类元素记为1另一类记为-1。有时候也会记成1和0但多数情况下用1/-1能直接把差值变成0视觉上更清晰。第二步前缀和。计算遍历到当前位置时的累计值cur。因为任意区间的和都能用两个前缀和之差表示所以“某段区间满足条件”等价于“某两个前缀和满足关系”。第三步哈希表。用哈希表存储已经出现过的前缀和。具体存什么取决于题目问的是“最长”“最短”还是“数量”求最长存最早出现位置。求最短存最近出现位置。求数量存出现次数。这个框架几乎可以套用到当前热门的“前缀和哈希表”系列题。3.2 相似题对照和为K的子数组、奇偶个数相等我先列几个和525非常像的题目放在一起看会更通透。题目题号核心条件哈希表存什么连续数组5250和1个数相等前缀和最早出现位置和为K的子数组560连续子数组和等于K前缀和出现次数和等于K的最长子数组325会员题连续子数组和等于K且最长前缀和最早出现位置每个元音包含偶数次的最长子字符串1371元音状态位相等状态码最早出现位置不过我要特别说说 LeetCode 560“和为K的子数组”它和525的区别很值得注意560统计的是“个数”所以哈希表里记录的是前缀和出现的次数525求最长的“长度”所以记录的是首次出现的位置。很多新手刷完525去刷560还沿用“存最早位置”的写法结果怎么算都少几个答案。这两个题的逻辑共同点是都依赖前缀和区别在于最终目标不同。还有一类变体是“奇偶个数相等”或“正负号差值相等”。比如给你一个数组求最长的子数组使得子数组内奇数和偶数的个数相等。处理方式一模一样奇数记为1偶数记为-1然后找和为0的最长子数组。3.3 与最长回文子串在思路上的根本差异LeetCode热门榜上还有一道题5. 最长回文子串。搜索热词里也有它。很多同学会把这两道题混在一起觉得都是“最长子串/子数组”解法应该类似。其实它们的思路差异非常大。最长回文子串的核心是对称性。它要求s[i..j]反转后和自己相等而不是要求某种数值累加为0。所以常见解法是中心扩展法以每个位置或者每两个位置中间为中心向两边扩展判断左右字符是否相等。也有动态规划做法dp[i][j]表示s[i..j]是否为回文串转移只看两端字符和中间子串。而525的核心是数值关系。它不关心子数组内部元素的排列只关心0和1数量是否相等。这使得我们能把数组里的元素替换成数值用前缀和来压缩区间信息。你非要说共同点那就是两者都要求“连续”的区间都需要枚举所有可能区间的能力。但一个是结构匹配一个是数值归零。刷题时如果能把这两类放到两套框架里思路会清爽很多。3.4 从525延伸到贪吃香蕉和目标和的方法论对比搜索热词里还有两个有代表性的题073 爱吃香蕉的狒狒实际上是875题和目标和494题。它们和525分属三种不同的解题范式值得放在一起对比。525 连续数组输入是一个数组要求返回某个区间的属性。解法方向是前缀和 哈希表把区间和转化为前缀和相等。875 爱吃香蕉的狒狒输入是香蕉堆数组和总时间要求最小速度。这是一个“最小值”问题通常用二分答案假设速度为mid计算是否能按时吃完然后不断缩小搜索范围。494 目标和输入一个数组和一个目标值要求通过添加或-号得到目标值的方案数。这是组合计数问题用动态规划或DFS记忆化。这三种题分别对应了“区间查询”“二分答案”“组合计数”三种常见的解题模型。如果你刷题时只看题解不看模型很容易出现“看一道会一道换一道就懵”的情况。所以从525出发把它抽象成“前缀和模型”再对比其他模型才是做知识点总结的正确姿势。4. 实战中的易错点、边界条件与刷题建议4.1mp[0] -1为什么是必须的这是525题最容易踩的坑。如果你忘记初始化first[0] -1会漏掉一类答案从数组开头开始的平衡子数组。我们看[0,1]如果哈希表初始为空i0cur-1不存在记录first[-1]0。i1cur00不存在于是记录first[0]1。遍历结束ans始终是0。正确答案是2因为你没有把cur0在位置-1出现这件事算进去。这种情况不仅在“整个数组刚好平衡”时发生而是所有“从开头某处到当前位置形成平衡子数组”都会被漏掉。因为前缀和第一次出现的位置如果不在哈希表里就无法形成差值。所以请记住前缀和的初始值0必须预先存入哈希表位置记为-1。4.2 负数前缀和与哈希表的兼容性因为把0替换成了-1所以前缀和cur可能是负数而且会在负数范围内波动。比如数组全是0cur会一路降到-n。那么哈希表的 key 就是负数。C 的unordered_mapint, int天然支持负数 keyPython 的dict也支持。如果你看到有人用数组替代哈希表那通常是因为前缀和范围已知且连续例如[-n, n]可以加一个偏移量n映射到[0, 2n]的下标。这也是一种写法但我个人更推荐直接用哈希表代码更易读也省去偏移量的脑子负担。不过如果你在面试现场想进一步省空间或者题目环境对哈希表不友好可以考虑数组偏移法。具体做法是先开一个大小为2*n3的数组索引cur n就是cur对应的位置初始化为-1然后逻辑和哈希表版本一致。不过这个写法在n很大的时候内存也会偏大面试时可以两种都提一下展示你懂优化空间。4.3 边界条件空数组、全0、全1虽然题目的约束通常保证nums.length 1但你还是要想清楚边界情况。空数组不存在任何子数组答案应该是0。如果你用题目给的函数签名空数组要返回0。数组长度为1一个元素不可能同时包含0和1答案应该是0。全0数组里面没有任何一个1所以0和1不可能相等答案0。全1数组同理答案0。交替数组例如[0,1,0,1]答案可以是整个数组长度为4。因为2个0、2个1。另外有个有趣的检查点答案一定是偶数。因为0和1个数相等子数组长度 0的个数 1的个数 2倍0的个数必然是偶数。所以如果你最后算出来一个奇数的最长长度那一定哪里出了问题可以用这个性质自测。4.4 空间优化与代码风格细节在代码层面有几个细节值得养成习惯不要显式构造前缀和数组。你只需要维护一个cur变量边遍历边更新。否则白白浪费O(n)额外空间。更新答案和记录首次位置的顺序。先判断cur是否已存在。如果存在更新答案如果不存在才记录first[cur] i。顺序反了会导致首次位置被覆盖成更晚的位置答案变小。使用if (first.find(cur) ! first.end())而不是if (first[cur])。后者会在 key 不存在时插入一个默认值污染哈希表。Python 里if cur in first不要写成if first.get(cur)因为first.get(cur)可能返回0位置0而0是假值会漏判。很多人在这里翻车当first[cur]恰好等于0时if (first[cur])为假导致逻辑错误。我们再看一个容易让人迷惑的点为什么i - first[cur]不会出现负数因为first[cur]一定是之前已经出现过的位置它必然小于当前的i。所以长度恒正。如果题目允许空子数组要初始化答案为0。5. 从525沉淀下来的刷题方法论5.1 一个可复用的解题模板刷完525我建议你把它抽象成一个模板以后遇到“最长连续子数组满足某个差值条件”的题直接套这个思路初始化 first {0: -1} cur 0 ans 0 遍历数组 cur 根据当前元素更新差值 if cur 在 first 中: ans max(ans, i - first[cur]) else: first[cur] i 返回 ans这个模板的关键是回答三个问题当前元素应该映射成什么数值需要满足的条件用前缀和怎么表达哈希表里存最早位置、最近位置还是出现次数比如把0换成-1条件变成cur相等这就是525。如果要求“和为K的最长连续子数组”那么把初始条件换成first {0: -1}遍历时cur nums[i]判断cur - K是否在哈希表里而不是判断cur。这也是一个高频变体建议自己写一遍。5.2 如何利用题目列表做知识点串联现在刷题平台很多题解也很丰富。但如果你只按题号顺序刷很难形成体系。我在刷完525之后专门用“前缀和”作为关键词搜索题库把相关的题目全都拉出来过了一遍。这里分享一个我自己的刷题顺序建议先从525入手理解0和1数量相等怎么转化为前缀和相等。然后刷560理解同一个框架下求“个数”和求“长度”的区别。接着刷1371把单独维度的前缀和扩展成状态压缩的前缀和对思维提升很大。有余力再刷1124表现良好的最长时间段条件从“和为0”变成“和大于0”要用单调栈辅助可以让理解更深一层。这样的专题刷法比每天随机刷题有效得多。因为所有题目背后的思考路径是相通的你只需要改变“映射规则”和“哈希表存储内容”同一套模板就能覆盖一大批题。5.3 我的个人体会与后续练习建议我第一次做525的时候其实并没有一眼看出前缀和的做法。我先试了滑动窗口越推越觉得别扭因为0和1数量相等并没有单调性窗口扩大不一定让“平衡”从无到有缩小也不一定让“平衡”消失。后来看到题解里“把0看成-1”这个操作拍大腿叫绝——它本质上是把“平衡”这个文字条件变成数学上“和为0”的精确表达。从那以后我养成了一个习惯遇到任何“找最长连续区间满足某个配对条件”的题先别急着写代码先问自己“这个条件能不能转化成数值能不能用前缀和的差值表示”如果能那大概率就是前缀和哈希表的题。最后给你一个小建议解完525后不要急着看下一题试着把题目的条件改一改比如“0和1个数差恰好为k的最短子数组”“0和1个数相等的子数组数量”用同样的思路去推一遍。你会发现525背后是一整个家族而你已经掌握了解开它们的那把钥匙。我自己在实际刷题中还有一个体会这类前缀和哈希表的题不是看懂了就会写而是要在纸上手动跑几个用例体会到哈希表“记录最早位置”到底在追踪什么信息。等你跑通了[0,1,0,1]和[0,0,1,0,0,0,1,1]这两个用例就再也不会怕它了。