线性动态规划：连续数组（Contiguous Array）

题目描述：
给定一个二进制数组 nums，你需要找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

例如：
输入：nums = [0,1,0]
输出：2
解释：最长连续子数组是 [0,1] 或 [1,0]，它们都含有相同数量的 0 和 1，长度为 2。

解题思路详解

第一步：理解问题核心

目标是在一个只包含 0 和 1 的数组中，找到一个连续子数组，其中 0 的数量等于 1 的数量。
最直接的想法是暴力枚举所有子数组，统计其中 0 和 1 的个数，但时间复杂度为 O(n²)，在 n 较大时（例如 10⁵）会超时。我们需要一种更高效的方法。

第二步：关键转化——将 0 视为 -1

如果我们把所有的 0 替换为 -1，那么原问题就转化为：
找到一个连续子数组，其元素之和为 0。
为什么呢？

• 子数组的和 = 1 的个数 × 1 + 0 的个数 × (-1) = (1 的个数) - (0 的个数)
• 当 1 的个数等于 0 的个数时，和为 0。

于是，问题变成了：在一个由 1 和 -1 组成的数组中，寻找和最长为 0 的连续子数组。

第三步：前缀和的应用

定义前缀和 prefix[i] 为从数组开头到第 i 个元素（索引 i-1）的和。
为了方便，我们通常定义 prefix[0] = 0，表示空前缀的和为 0。
对于子数组 nums[i:j]（左闭右开），其和 = prefix[j] - prefix[i]。
我们要找的就是 prefix[j] - prefix[i] = 0，即 prefix[j] = prefix[i] 的情况。
所以，问题转化为：找到两个下标 i 和 j（i < j），使得 prefix[i] = prefix[j]，并且 j-i 尽可能大。

第四步：如何高效查找

我们可以在一次遍历中，记录每个前缀和第一次出现的位置（即最小的下标）。
如果当前前缀和之前已经出现过，假设第一次出现在位置 first，那么从 first+1 到当前下标 curr 这个子数组的和就是 0，长度为 curr - first。
我们不断更新最大长度即可。

具体步骤：

1. 初始化一个哈希表 map，键为前缀和，值为该前缀和第一次出现的下标。
2. 初始状态：map[0] = 0，表示前缀和为 0 出现在下标 0 之前（即空数组）。
3. 遍历数组，维护当前前缀和 sum。
   • 如果当前 sum 在 map 中存在，说明从 map[sum] 到当前下标的子数组和为 0，更新最大长度。
   • 如果不存在，将当前 sum 和当前下标存入 map（只存第一次出现的位置）。
4. 遍历完成后，最大长度即为答案。

第五步：举例说明

以 nums = [0,1,0] 为例：

1. 将 0 替换为 -1，数组变为 [-1, 1, -1]。
2. 初始化：map = {0: 0}, sum = 0, max_len = 0。
3. 下标 0：sum = 0 + (-1) = -1，-1 不在 map 中，存入 map[-1] = 1（这里下标从 1 开始计，表示到第 1 个元素之后的前缀和）。实际代码中下标从 0 开始遍历元素，需注意下标偏移，下面用实际索引说明：

实际遍历（索引从 0 开始）：

• i=0, num=-1: sum = -1，map 中无 -1，存入 map[-1]=0。
• i=1, num=1: sum = -1+1=0，map 中有 0（对应下标 -1，表示空数组），当前子数组长度为 i - map[0] = 1 - (-1) = 2，更新 max_len=2。
• i=2, num=-1: sum = 0-1=-1，map 中有 -1（对应下标 0），当前子数组长度为 i - map[-1] = 2-0=2，max_len 仍为 2。

所以最大长度为 2。

第六步：算法实现（伪代码）

function findMaxLength(nums):
    map = {0: -1}  # 前缀和0出现在下标-1（空前缀）
    sum = 0
    max_len = 0
    for i from 0 to len(nums)-1:
        if nums[i] == 0:
            sum -= 1
        else:
            sum += 1
        if sum in map:
            max_len = max(max_len, i - map[sum])
        else:
            map[sum] = i
    return max_len

时间复杂度 O(n)，空间复杂度 O(n)（最坏情况需要存储 n 个不同的前缀和）。

第七步：边界情况与测试

• 空数组：返回 0。
• 全 0 或全 1：不可能有相同数量的 0 和 1，返回 0。
• 大规模数组：算法依然高效。

例如 nums = [0,1,1,0,1,1,1,0]：
转化为 [-1,1,1,-1,1,1,1,-1]
前缀和序列：0, -1, 0, 1, 0, 1, 2, 3, 2
最长相等前缀和距离：前缀和 0 出现在下标 -1 和 2，距离 3（子数组 [0,1,1,0] 长度 4？这里注意：下标 2 对应原始数组的前三个元素，和下标 -1 的距离是 3，表示子数组长度为 3？我们需要仔细验证）

实际计算：

• i=0, sum=-1 → 存(-1,0)
• i=1, sum=0 → 已有0在-1，长度=1-(-1)=2
• i=2, sum=1 → 存(1,2)
• i=3, sum=0 → 已有0在-1，长度=3-(-1)=4 → 更新 max_len=4
• i=4, sum=1 → 已有1在2，长度=4-2=2
• i=5, sum=2 → 存(2,5)
• i=6, sum=3 → 存(3,6)
• i=7, sum=2 → 已有2在5，长度=7-5=2
  最终 max_len=4，对应原始子数组 [0,1,1,0] 确实有 2 个 0 和 2 个 1。

第八步：总结

这道题的核心在于将原问题通过 0→-1 的转换，变为寻找和为 0 的最长子数组，进而利用前缀和+哈希表在 O(n) 时间内解决。这是一种典型的“前缀和+哈希记录首次出现位置”的思路，适用于处理子数组和类问题。