连续数组 题目描述 给定一个二进制数组 nums （只包含 0 和 1），找到含有相同数量的 0 和 1 的 最长连续子数组 ，并返回该子数组的长度。 示例 1 输入：nums = [ 0,1 ] 输出：2 解释：[ 0, 1 ] 是含有相同数量 0 和 1 的最长连续子数组，长度为 2。 示例 2 输入：nums = [ 0,1,0 ] 输出：2 解释：[ 0, 1] 或 [ 1, 0] 长度为 2，但整个数组 [ 0,1,0 ] 中 0 有 2 个，1 有 1 个，数量不同。 解题过程循序渐进讲解 步骤 1：理解问题核心 题目要求子数组中 0 和 1 的数量相等，且是 连续 的。 直接遍历所有子数组并统计 0 和 1 的个数会非常慢（O(n³) 或 O(n²)），需要优化。 步骤 2：转化为“和为零”的问题 一个常见技巧是： 将所有的 0 替换为 -1 那么“0 和 1 数量相等” ⇔ “子数组元素和为 0” 例如： nums = [ 0, 1, 0 ] 替换为 [ -1, 1, -1 ] 子数组 [ 0,1] 对应 [ -1, 1 ] 和为 0。 子数组 [ 1,0] 对应 [ 1, -1 ] 和为 0。 问题转化为：在转换后的数组中， 找最长的和为 0 的连续子数组 。 步骤 3：引入前缀和 定义前缀和 prefix[i] 为前 i 个元素的和（i 从 0 开始，prefix[ 0 ] = 0 表示前 0 个元素的和）。 转换后数组为 arr，长度 n。 子数组 arr[ i:j] 的和 = prefix[ j+1] - prefix[ i ]。 我们需要： prefix[ j+1] - prefix[ i ] = 0 ⇒ prefix[ j+1] = prefix[ i ] 问题进一步转化为 ： 在 prefix 数组中，找到两个相等的值，且它们的下标差（j+1 - i）最大。 步骤 4：用哈希表记录最早出现的位置 遍历 prefix 数组，用哈希表 map 记录每个前缀和 第一次出现 的下标。 当遍历到下标 k 时： 如果当前前缀和 cur_ sum 之前出现过（在 map 中存在）， 则从第一次出现的下标 map[ cur_ sum ] 到当前下标 k 之间的子数组和为 0， 子数组长度为 k - map[ cur_ sum ]，更新最大长度。 初始化 ： map[ 0 ] = -1 表示前缀和 0 在“第 0 个元素之前”已经出现（即空数组），这样当从开头到某位置的子数组和为 0 时也能计算长度。 步骤 5：一步一步推演例子 nums = [ 0,1,0,0,1,1,0 ] 转换 0→-1, 1→1： arr = [ -1, 1, -1, -1, 1, 1, -1 ] 计算前缀和并记录最早出现位置： | 下标 | 元素 | 当前前缀和 cur_ sum | map 记录 (cur_ sum → 最早下标) | 是否出现过？ | 长度计算 | |------|------|-------------------|-------------------------------|--------------|----------| | -1 | | 0 | {0: -1} | 初始化 | | | 0 | -1 | -1 | {0:-1, -1:0} | 否 | | | 1 | 1 | 0 | 0 出现过，最早下标 -1 | 是 | 1 - (-1) = 2 | | 2 | -1 | -1 | -1 出现过，最早下标 0 | 是 | 2 - 0 = 2 | | 3 | -1 | -2 | {0:-1, -1:0, -2:3} | 否 | | | 4 | 1 | -1 | -1 出现过，最早下标 0 | 是 | 4 - 0 = 4 | | 5 | 1 | 0 | 0 出现过，最早下标 -1 | 是 | 5 - (-1) = 6 | | 6 | -1 | -1 | -1 出现过，最早下标 0 | 是 | 6 - 0 = 6 | 最大长度是 6，对应子数组是 nums[ 0:5] 即 [ 0,1,0,0,1,1 ]（3 个 0 和 3 个 1）。 步骤 6：算法复杂度 时间复杂度：O(n)，一次遍历。 空间复杂度：O(n)，哈希表存储最多 n+1 个前缀和。 关键点总结 将 0 替换为 -1，将“0 和 1 数量相等”转化为“子数组和为 0”。 用前缀和之差表示子数组和，则问题转化为在 prefix 中找两个相等值的最大距离。 用哈希表存储每个前缀和 最早出现 的下标，遍历时快速判断。 初始化 map[ 0 ] = -1 很重要，确保从头开始的合法子数组能被计算。 这个解法巧妙地利用哈希表将看似复杂的问题降低到线性时间，是前缀和+哈希表的经典应用。