题目：线性动态规划：连续数组（Contiguous Array）
一、题目描述
给定一个二进制数组 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。
示例 3：
输入：nums = [0,0,1,0,1,1,0]
输出：6
解释：子数组 [0,0,1,0,1,1] 或 [0,1,0,1,1,0] 包含相同数量的 0 和 1，长度为 6。
二、问题分析
我们要求一个连续子数组，其中 0 和 1 的数量相等。
直接枚举所有子数组并统计其中 0 和 1 的个数，时间复杂度为 \(O(n^2)\)，在数组较长时效率太低。
我们需要一种更聪明的方法，将问题转化为更易处理的形式。
三、关键思路转化
核心技巧：将 0 视为 -1，将 1 视为 +1。
这样，如果一个子数组中 0 和 1 的数量相等，那么该子数组的“和”就是 0。
举例：
数组 [0, 1, 0, 0, 1, 1, 0] 转化为
[-1, +1, -1, -1, +1, +1, -1]。
问题就转化为：寻找和为零的最长子数组。
四、动态规划思路（实际上是前缀和 + 哈希表）
这个问题虽然归类为“线性动态规划”，但它更常见的解法是使用前缀和和哈希表来在线性时间内解决。
我们定义一个变量 prefix_sum，表示从数组开头到当前位置的累加和（按上述 -1/+1 转换规则）。
我们希望找到两个位置 i 和 j（j > i），使得：
\[\text{prefix\_sum}[j] - \text{prefix\_sum}[i] = 0 \]
这意味着从 i+1 到 j 的子数组和为 0，即 0 和 1 的数量相等。
所以，问题变成：寻找两个前缀和相等的最远距离。
五、逐步解法
-
初始化：
- 用变量
current_sum记录当前前缀和，初始为 0。 - 用哈希表
map记录每个前缀和第一次出现的位置（索引）。 - 将
(0, -1)存入哈希表，表示前缀和为 0 出现在索引 -1（即数组开始之前）。
- 用变量
-
遍历数组：
- 对于每个元素
nums[i]：- 如果
nums[i] == 0，则current_sum -= 1。 - 如果
nums[i] == 1，则current_sum += 1。
- 如果
- 检查
current_sum是否已经在哈希表中：- 如果存在，说明从之前第一次出现该前缀和的位置的下一个索引到当前位置，子数组和为 0。
更新最大长度：max_len = max(max_len, i - map[current_sum])。 - 如果不存在，将
(current_sum, i)存入哈希表。
- 如果存在，说明从之前第一次出现该前缀和的位置的下一个索引到当前位置，子数组和为 0。
- 对于每个元素
-
遍历完成后，
max_len即为所求。
六、举例推演
以 nums = [0, 1, 0, 0, 1, 1, 0] 为例：
| 索引 i | nums[i] | current_sum | 哈希表记录（前缀和 → 第一次出现的索引） | 最大长度更新 |
|---|---|---|---|---|
| -1 | - | 0 | {0: -1} | - |
| 0 | 0 | -1 | {0: -1, -1: 0} | - |
| 1 | 1 | 0 | {0: -1, -1: 0} | 1 - (-1) = 2 |
| 2 | 0 | -1 | {0: -1, -1: 0} | 2 - 0 = 2 |
| 3 | 0 | -2 | {0: -1, -1: 0, -2: 3} | - |
| 4 | 1 | -1 | {0: -1, -1: 0, -2: 3} | 4 - 0 = 4 |
| 5 | 1 | 0 | {0: -1, -1: 0, -2: 3} | 5 - (-1) = 6 |
| 6 | 0 | -1 | {0: -1, -1: 0, -2: 3} | 6 - 0 = 6 |
最终最大长度为 6。
七、代码实现（Python）
def findMaxLength(nums):
# 哈希表记录前缀和第一次出现的索引
sum_to_index = {0: -1}
current_sum = 0
max_len = 0
for i, num in enumerate(nums):
# 将0视为-1，1视为+1
current_sum += 1 if num == 1 else -1
if current_sum in sum_to_index:
# 如果之前出现过相同的前缀和，计算当前子数组长度
max_len = max(max_len, i - sum_to_index[current_sum])
else:
# 第一次出现该前缀和，记录索引
sum_to_index[current_sum] = i
return max_len
八、复杂度分析
- 时间复杂度：\(O(n)\)，只遍历数组一次。
- 空间复杂度：\(O(n)\)，哈希表最多存储 \(n+1\) 个不同的前缀和。
九、总结
本题的核心是将“0 和 1 数量相等”转化为“子数组和为 0”，再通过前缀和与哈希表记录第一次出现的位置，从而在 \(O(n)\) 时间内找到最长满足条件的连续子数组。
这是一种典型的“前缀和+哈希表”技巧，在解决连续子数组相关问题时非常有用。