欢迎阅读 欢迎来到「连续数组」题解之旅本文将带你从在 0 和 1 组成的序列中找最长的一段让两种数字一样多这一直观场景出发深入理解前缀和 哈希表的巧妙运用并掌握如何把 0 映射为 -1来把数量相等转化为前缀和相等从而求出最长连续子数组。在开始之前建议你先了解题目背景这是 LeetCode 525 题给定二进制数组nums找出含有相同数量 0 和 1的最长连续子数组返回其长度。本质上把 0 看作 -1 后0 和 1 数量相等 ⇔ 子数组和为 0问题转化为找和为 0 的最长子数组。明确学习目标掌握0→-1 的映射技巧理解哈希表存最早下标而非计数的原因并熟练处理hash[0] -1 的初始化与重复前缀和等边界情况。准备好环境建议在本地 IDE 或 LeetCode 在线编辑器中打开代码边看边运行亲手验证示例如nums [0,1]输出2nums [0,1,0]输出2。本文将从问题转化、前缀和相等、最早下标记录、边界防护到代码实现层层递进。即使你对前缀和变式还不熟悉我们也会从把 0 当 -1账本归零的那段就是平衡段这一直觉出发让你轻松抓住核心思想——0 变 -1前缀和重逢处即平衡段。现在让我们一起映射 0 为 -1找出最长的平衡子数组吧 ⚖️个人主页愿旖旎专栏传送门算法专栏当前学习内容前缀和一.题目525. 连续数组 - 力扣LeetCode​二、算法分析一、问题分析前置分析题目要求在二进制数组nums只含 0、1中找出0 和 1 数量相等的最长连续子数组返回长度。关键约束元素只有0 和 1要求最长可能不存在满足条件的子数组返回 0。核心思路暴力枚举所有子数组统计 0/1 数量总代价 O(n²)把 0 映射为 -1后子数组 0 和 1 数量相等 ⇔子数组和为 0⇔两端前缀和相等用哈希表记录每个前缀和最早出现的下标O(n) 求出最长长度。 例子0 变 -1 的神奇效果nums [0, 1, 0]把 0 变 -1 后为[-1, 1, -1]。子数组[0..1]-110和[1..2]1-10的和都是 0对应原数组[0,1]和[1,0]——0 和 1 各一个数量相等。反之若 0 保持 0[0,1]的和是 1看不出数量相等映射后数量相等 ⇔ 和为 0一目了然。二、算法策略0→-1 映射 前缀和最早下标核心步骤映射把nums中所有 0 改为 -1原数组原地修改。初始化hash[0] -1空前缀和 0 出现在下标 -1、sum 0、ret 0。遍历累加sum nums[i]得到当前前缀和。查询配对若哈希表已有该前缀和说明从最早出现处到当前和为 0ret max(ret, i - hash[sum])否则记录最早下标hash[sum] i。返回遍历结束返回ret。 示例nums [0, 1, 0]映射后[-1, 1, -1]步骤isum查询 hash操作ret初始化—0—hash{-1: -1}0i0, x-10-1无 hash[-1]记录 hash[-1] 00i1, x110有 hash[0] -1ret max(0, 1-(-1)) 22i2, x-12-1有 hash[-1] 0ret max(2, 2-0) 22i1时sum0重逢空前缀下标 -1长度1-(-1)2子数组[0..1]i2时sum-1重逢下标 0长度2-02子数组[1..2]——最长 2 ✅与题目示例一致。三、正确性说明简单版本映射等价0 变 -1 后子数组元素和 (#1) - (#0)和为 0 ⇔#1 #0与数量相等逐字等价不会错判。前缀和相等判定子数组[j1..i]和为 0 ⇔sum[i] sum[j]两端前缀和相等数学上严格成立。最早下标保证最长同一前缀和第一次出现的位置最早i - 最早下标得到的子数组最长ret max逐步更新即全局最长不漏最优。hash[0] -1 覆盖起点从下标 0 开始的平衡子数组对应空前缀和 0下标 -1初始化使这类起点类子数组也能被统计不漏解。 例子为什么存最早下标而非计数nums [1, 0, 0, 1]映射后[1, -1, -1, 1]前缀和为1、0、-1、0。sum0出现两次i1、i3若只记出现过i3 时配对长度是3-12但最早的下标 1 之前还有空前缀下标 -1i3与-1配对长度3-(-1)4整个数组[1,0,0,1]两个 1 两个 0——只有保留最早下标才能找到最长存计数或最新下标都会漏掉最长解。四、实现细节边界防护初始化hash[0] -1空前缀和 0 的下标是 -1、sum 0、ret 0。边界防护原地修改0 为 -1 不影响正确性后续只用到映射后的值hash.count(sum)判断是否出现过——出现过则只更新 ret 不更新下标保留最早未出现过才记录下标全数组无平衡子数组时ret保持 0。复杂度时间 O(n)单次遍历 预处理映射 O(n)空间 O(n)哈希表最多存 n 个前缀和。关键操作if (x 0) x -1;映射、if (hash.count(sum)) ret max(ret, i - hash[sum]); else hash[sum] i;配对/记录、hash[0] -1;空前缀初始化。 例子为什么 hash[0] -1 而不是 0nums [0, 1]映射后[-1, 1]i0时sum-1记录hash[-1]0i1时sum0重逢空前缀。若hash[0] 0错误配对长度1-01漏掉整个数组[0,1]长度 2正确的hash[0] -1使长度1-(-1)2✅——空前缀出现在第 -1 个位置这是起点类子数组正确计长的关键。五、返回值目标映射返回ret0 和 1 数量相等的最长连续子数组长度对应题目返回该子数组的长度。三.代码class Solution { public: int findMaxLength(vectorint nums) { unordered_mapint, int hash; // 哈希表前缀和 - 最早出现的下标 // 1. 映射把 0 变成 -1使0 和 1 数量相等等价于子数组和为 0 for (auto x : nums) { if (x 0) { x -1; } } hash[0] -1; // 空前缀和为 0出现在下标 -1虚构位置 int sum 0; // 当前前缀和 int ret 0; // 答案最长平衡子数组长度 // 2. 单次遍历找前缀和重逢的最远距离 for (int i 0; i nums.size(); i) { sum nums[i]; // 当前位置的前缀和 if (hash.count(sum)) { // 该前缀和之前出现过从最早出现处到 i 的和为 0即平衡子数组 ret max(ret, i - hash[sum]); } else { hash[sum] i; // 首次出现记录下标保留最早才能最长 } } return ret; // 3. 返回最长长度 } };四、易错点分析难点1为什么要把 0 映射成 -1for (auto x : nums) { if (x 0) { x -1; // 0 - -1 } }若 0 保持 0子数组和只反映 1 的个数无法表达0 的个数映射后子数组和 (#1) - (#0)和为 0 ⇔ 0 和 1 数量相等。这一步是问题转化的核心——把数量比较变成和为零从而能用前缀和解决。漏掉映射会退化为找和为 0 的原数组子数组0 和 1 各一个时和为 1永远找不到。难点2为什么哈希表存最早下标而不是计数if (hash.count(sum)) ret max(ret, i - hash[sum]); else hash[sum] i; // 首次出现才记录本题求的是最长长度同一前缀和出现多次时第一次出现的位置最左i - 最早得到最长子数组。若每次都更新hash[sum] i存最新下标长度会越算越短若像 560/974 那样存计数则无法计算长度。求个数存计数、求长度存最早下标是这两类题的分水岭。难点3hash[0] -1的初始化最容易写错hash[0] -1; // 空前缀和 0出现在下标 -1从下标 0 开始的平衡子数组如[0,1]整体对应空前缀其下标是虚构的-1。若误写hash[0] 0起点类子数组长度会少算 1如[0,1]得 1 而非 2若漏掉初始化sum首次归零时走 else 分支记录当前下标起点类子数组彻底漏计。-1 代表数组之前的虚拟位置是本题边界的关键。难点4找到重复前缀和时只更新 ret不更新下标if (hash.count(sum)) { ret max(ret, i - hash[sum]); // 不执行 hash[sum] i } else { hash[sum] i; }若在已存在分支里也执行hash[sum] i最早下标被覆盖成最新后续再遇到该前缀和时长度必然变小最长解丢失。count分支与else分支必须互斥——出现过就只算长度没出现过才记录二者不可同时执行。五、流程图 闭幕 恭喜你完成了「连续数组0和1数量相等的最长子数组」问题的学习为了巩固知识并进一步拓展建议你动手实践在 LeetCode 上提交代码尝试不同的测试用例。深入思考本题将0 映射为 -1使“0和1数量相等”等价于“子数组和为0”。为什么这种映射是有效的如果直接统计0和1的数量差能否得到相同的效果hash[0] -1表示空前缀和0出现在下标-1。为什么用 -1 而不是 0如果用 0计算长度时会出现什么偏差请举例说明。遍历过程中如果sum已存在于哈希表中直接计算i - hash[sum]更新答案否则记录当前下标。为什么不需要像“和为K的子数组”那样累加次数两者的目标有何不同如果数组全为0或全为1算法会返回什么请分析这种情况下hash的更新和ret的变化。如果你觉得本文对你有所帮助欢迎点赞 / 收藏关注作者获取更多题解留言交流你的疑问或优化思路深入思考答案映射有效性将 0 变为 -1 后子数组中 0 和 1 数量相等意味着 -1 和 1 的数量相等总和为 0。这种转换将原问题转化为求和为 0 的最长子数组可以利用前缀和差值快速求解与直接统计数量差本质等价但便于用哈希表统一处理。用 -1 而非 0hash[0] -1表示空前缀出现在下标 -1这样当sum再次为 0 时长度为i - (-1) i 1正确统计从数组开头到 i 的完整子数组长度若用 0则长度为i - 0 i会漏掉第一个元素结果少 1。不累加次数是因为本题求的是最大长度而非组合个数。只需知道该前缀和最早出现的位置计算当前与最早的距离即可无需统计次数。全为 0 或全为 1时若全为 0映射后全 -1前缀和递减每个前缀和都是首次出现hash不断记录新下标ret始终为 0返回 0正确因为没有 1 能平衡 0。全为 1 同理返回 0。祝你在算法之路上越走越稳早日攻克每一道难题下次见 ✨