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

题目描述：
给定一个只包含 0 和 1 的二进制数组 nums，你需要找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例：
输入：nums = [0,1,0]
输出：2
解释：最长连续子数组是 [0,1] 或 [1,0]，它们都含有相同数量的 0 和 1。

1. 问题分析

• 目标：找到最长的连续子数组，其中 0 和 1 的数量相等。
• 关键点：子数组必须是连续的，且只包含 0 和 1。
• 难点：如果直接暴力枚举所有子数组，时间复杂度为 O(n²)，在数组长度较大时会超时。
  我们需要一种更高效的方法，将问题转化为“前缀和”相关的问题。

2. 核心思路：将 0 视为 -1

如果我们把数组中的 0 都看作 -1，那么：

• 原数组中 0 和 1 的数量相等 ⇔ 新数组中子数组的元素和为 0。
• 这样问题就转化为：在新数组（元素为 1 或 -1）中，寻找最长的和为 0 的连续子数组。

3. 引入前缀和

定义前缀和 prefix_sum[i] 表示新数组从第 0 个元素到第 i-1 个元素的和（即前 i 个元素的和，其中 prefix_sum[0] = 0）。
那么子数组 [i, j] 的和为 prefix_sum[j+1] - prefix_sum[i]。
我们希望这个差值为 0，即：

prefix_sum[j+1] = prefix_sum[i]

也就是说，我们需要找到两个下标 i 和 j（i < j），使得它们的前缀和相等。
此时子数组长度 = j - i。

4. 问题转化

问题变成了：遍历前缀和数组，对于每个前缀和的值，记录它第一次出现的下标。
当再次遇到相同的前缀和时，用当前下标减去第一次出现的下标，就得到一个和为 0 的子数组长度。
我们取所有这样的长度的最大值。

举例：
原数组 nums = [0,1,0]
新数组（0→-1, 1→1）：[-1, 1, -1]
前缀和 prefix = [0, -1, 0, -1]

• prefix[0] = 0（下标 0）
• prefix[1] = -1（下标 1）
• prefix[2] = 0（下标 2），此时与 prefix[0] 相等，子数组长度为 2 - 0 = 2。
• prefix[3] = -1（下标 3），与 prefix[1] 相等，子数组长度为 3 - 1 = 2。
  所以最长长度为 2。

5. 动态规划（哈希表实现）

我们可以用一次遍历完成计算，使用哈希表记录每个前缀和第一次出现的下标。
初始化：哈希表 map，map[0] = -1，表示前缀和为 0 在“下标 -1”处出现（这是虚拟起点，方便计算长度）。
遍历原数组，维护当前前缀和 cur_sum，并更新哈希表和最大长度：

• 如果 cur_sum 已经在哈希表中，则计算当前下标与第一次出现的下标之差，更新最大长度。
• 如果 cur_sum 不在哈希表中，则将其存入哈希表，值为当前下标。

这样，每个前缀和只记录第一次出现的位置，保证子数组长度最大。

6. 逐步演算

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

1. map = {0: -1}, cur_sum = 0, max_len = 0。
2. i=0, num=0 → cur_sum = -1，不在 map 中，map[ -1 ] = 0。
3. i=1, num=1 → cur_sum = 0，已在 map 中，子数组长度 = 1 - (-1) = 2，max_len = 2。
4. i=2, num=0 → cur_sum = -1，已在 map 中，长度 = 2 - 0 = 2，max_len 仍为 2。
5. i=3, num=1 → cur_sum = 0，已在 map 中，长度 = 3 - (-1) = 4，max_len = 4。
6. i=4, num=1 → cur_sum = 1，不在 map 中，map[1] = 4。
7. i=5, num=0 → cur_sum = 0，已在 map 中，长度 = 5 - (-1) = 6，max_len = 6。
8. i=6, num=0 → cur_sum = -1，已在 map 中，长度 = 6 - 0 = 6，max_len 仍为 6。

最终结果：6（对应子数组 [1,0,1,1,0,0] 或整个数组去掉第一个 0 之后的部分，其中 0 和 1 各三个）。

7. 代码框架（Python）

def findMaxLength(nums):
    map = {0: -1}
    cur_sum = 0
    max_len = 0
    for i, num in enumerate(nums):
        cur_sum += 1 if num == 1 else -1
        if cur_sum in map:
            max_len = max(max_len, i - map[cur_sum])
        else:
            map[cur_sum] = i
    return max_len

时间复杂度：O(n)，只需一次遍历。
空间复杂度：O(n)，哈希表最多存储 n+1 个前缀和。

8. 关键点总结

• 将 0 转换为 -1 是核心技巧，从而将“数量相等”转化为“和为 0”。
• 利用前缀和相等来寻找和为 0 的子数组。
• 哈希表记录前缀和第一次出现的下标，保证得到最长的子数组。
• 初始化 map[0] = -1 处理从第一个元素开始就满足条件的情况。

这个解法是典型的“前缀和 + 哈希表”结合，是线性动态规划中处理子数组和问题的常用方法。