企业官网建设流程全解析

👋 欢迎阅读

🎯 欢迎来到「连续数组」题解之旅！本文将带你从"在 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]输出2，nums = [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]（-1+1=0）和[1..2]（1-1=0）的和都是 0，对应原数组[0,1]和[1,0]——0 和 1 各一个，数量相等。反之若 0 保持 0，[0,1]的和是 1，看不出"数量相等"；映射后"数量相等 ⇔ 和为 0"一目了然。

二、算法策略（0→-1 映射 + 前缀和最早下标）

核心步骤：

1. 映射：把nums中所有 0 改为 -1（原数组原地修改）。
2. 初始化：hash[0] = -1（空前缀和 0 出现在下标 -1）、sum = 0、ret = 0。
3. 遍历累加：sum += nums[i]得到当前前缀和。
4. 查询配对：若哈希表已有该前缀和（说明从最早出现处到当前，和为 0），ret = max(ret, i - hash[sum])；否则记录最早下标hash[sum] = i。
5. 返回：遍历结束返回ret。

📊 示例（nums = [0, 1, 0]，映射后[-1, 1, -1]）：

i=1时sum=0重逢空前缀（下标 -1），长度1-(-1)=2（子数组[0..1]）；i=2时sum=-1重逢下标 0，长度2-0=2（子数组[1..2]）——最长 2 ✅，与题目示例一致。

三、正确性说明（简单版本）

• 映射等价：0 变 -1 后，子数组元素和 =(#1) - (#0)；和为 0 ⇔#1 == #0，与"数量相等"逐字等价，不会错判。
• 前缀和相等判定：子数组[j+1..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。sum=0出现两次（i=1、i=3）：若只记"出现过"，i=3 时配对长度是3-1=2，但最早的下标 1 之前还有空前缀（下标 -1），i=3与-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 而不是 0

nums = [0, 1]（映射后[-1, 1]）：i=0时sum=-1记录hash[-1]=0；i=1时sum=0重逢空前缀。若hash[0] = 0（错误），配对长度1-0=1，漏掉整个数组[0,1]（长度 2）；正确的hash[0] = -1使长度1-(-1)=2✅——空前缀"出现在第 -1 个位置"，这是起点类子数组正确计长的关键。

五、返回值（目标映射）

• 返回ret：0 和 1 数量相等的最长连续子数组长度，对应题目"返回该子数组的长度"。

三.代码

class Solution { public: int findMaxLength(vector<int>& nums) { unordered_map<int, 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 映射成 -1

for (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 那样存计数，则无法计算长度。"求个数存计数、求长度存最早下标"是这两类题的分水岭。

难点3：hash[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 而非 0：hash[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。

祝你在算法之路上越走越稳，早日攻克每一道难题！下次见 🚀✨