哈希算法题目：连续数组 题目描述 给定一个二进制数组 nums ，你需要找到其中包含相同数量的 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,1,0] 输出: 8 解释: 子数组 [0,0,1,0,1,1,0,1] 中，0 的数量是 4，1 的数量也是 4。 解题过程循序渐进讲解 第一步：理解问题核心与难点 问题的核心是，在一个只包含 0 和 1 的数组中，寻找一个 连续 的子数组，使得其中 0 的个数等于 1 的个数。 直观的暴力解法是，枚举所有可能的子数组起点和终点，然后统计其中 0 和 1 的数量是否相等。但这样的时间复杂度是 O(n³) 或 O(n²)（如果优化统计过程），对于较大的数组（n 可达 10⁵）来说是不可接受的。 我们需要一个更聪明的方法，将问题转化为一个能用哈希表高效解决的问题。 第二步：关键转化——从“计数”到“前缀和”与“差值” 核心观察 ：如果我们将数组中的 0 替换为 -1 ，问题会发生什么变化？ 原数组中 0 和 1 的数量相等，等价于替换后，新数组中所有元素之和为 0。 例如， [0, 1, 0, 1] 替换为 [-1, 1, -1, 1] ，总和为 0。 引入前缀和 ：对于一个数组， prefix_sum[i] 表示从数组开头到第 i 个元素（索引 i-1）的累积和。 对于替换后的数组 transformed_nums ， prefix_sum[i] 表示前 i 个元素的和。 子数组和与前缀和的关系 ：子数组 nums[j...i] (j < i) 的和，等于 prefix_sum[i+1] - prefix_sum[j] 。 我们希望子数组的和为 0。即 prefix_sum[i+1] - prefix_sum[j] = 0 。 这可以推导出： prefix_sum[i+1] = prefix_sum[j] 。 结论 ：寻找包含相同数量 0 和 1 的最长连续子数组， 等价于 在将 0 转换为 -1 后，寻找两个索引 j 和 i (j < i)，使得它们对应的前缀和 prefix_sum[j] 和 prefix_sum[i+1] 相等。子数组的长度就是 (i+1) - j 。 第三步：算法设计思路 初始化 ： 定义一个变量 current_sum 来动态计算前缀和，初始为 0。 定义一个哈希表 sum_to_index ，用来存储 每个前缀和的值第一次出现时对应的索引 。键是前缀和的值，值是计算到这个前缀和时对应的原始数组索引。 非常重要的一步：由于子数组可以从数组头部开始（即 j=0），我们需要预先处理前缀和为 0 的情况。我们在哈希表中存入 (0, -1) 。这表示，在遍历开始前（索引为 -1 的位置），前缀和已经是 0。这样，当我们后续遇到前缀和为 0 时，就能正确计算出从数组开头到当前位置的子数组长度。 遍历数组 ： 从左到右遍历原始数组 nums 的每个元素。 如果当前元素是 0，则 current_sum -= 1 ；如果是 1，则 current_sum += 1 。 检查 current_sum 这个值是否已经在哈希表 sum_to_index 中出现过。 如果出现过 ：设它第一次出现的索引为 first_index 。那么从 first_index + 1 到当前位置 i 的这个子数组，其和必然为 0（因为首尾前缀和相等）。计算子数组长度 i - first_index ，并更新最大长度 max_len 。 如果没出现过 ：将 (current_sum, i) 这个键值对存入哈希表。我们只记录第一次出现的位置，因为这样能保证当再次遇到相同前缀和时，计算出的子数组长度是最长的。 输出结果 ：遍历结束后， max_len 就是答案。 第四步：逐步推演示例 以 nums = [0, 0, 1, 0, 1, 1, 0, 1, 0] 为例。 | 索引 i | nums[ i] | 转换值 | current_ sum (前缀和) | 哈希表记录 (和: 首次索引) | 当前遇到的和是否在表中？ | 计算子数组长度 | 更新 max_ len | | :---- | :------ | :----- | :------------------- | :------------------------ | :---------------------- | :------------ | :---------- | | 初始化 | | | 0 | {0: -1} | | | max_ len = 0 | | 0 | 0 | -1 | -1 | {0: -1, -1: 0 } | 否，记录 | | 0 | | 1 | 0 | -1 | -2 | {0:-1, -1:0, -2:1 } | 否，记录 | | 0 | | 2 | 1 | 1 | -1 | {0:-1, -1:0, -2:1} | 是，首次在索引0 | 2 - 0 = 2 | 2 | | 3 | 0 | -1 | -2 | {0:-1, -1:0, -2:1} | 是，首次在索引1 | 3 - 1 = 2 | 2 | | 4 | 1 | 1 | -1 | {0:-1, -1:0, -2:1} | 是，首次在索引0 | 4 - 0 = 4 | 4 | | 5 | 1 | 1 | 0 | {0:-1, -1:0, -2:1} | 是，首次在索引-1 | 5 - (-1) = 6 | 6 | | 6 | 0 | -1 | -1 | {0:-1, -1:0, -2:1} | 是，首次在索引0 | 6 - 0 = 6 | 6 | | 7 | 1 | 1 | 0 | {0:-1, -1:0, -2:1} | 是，首次在索引-1 | 7 - (-1) = 8 | 8 | | 8 | 0 | -1 | -1 | {0:-1, -1:0, -2:1} | 是，首次在索引0 | 8 - 0 = 8 | 8 | 最终 max_len = 8 ，对应子数组为索引 0 到索引 7（即示例中给出的子数组）。注意，在索引8计算出的长度也是8，但起始点不同。 第五步：复杂度分析与总结 时间复杂度 ：O(n)。我们只需要遍历数组一次，每次操作（计算当前和、哈希表查询、哈希表插入）的时间复杂度都是 O(1)。 空间复杂度 ：O(n)。在最坏情况下，可能需要存储 n 个不同的前缀和值到哈希表中。 核心要点 ： 这道题的精妙之处在于将原始的“计数相等”问题，通过 将 0 视为 -1 ，转化为 子数组和为 0 的问题。再通过 前缀和 的技巧，将“子数组和为 0”转化为寻找 两个相等的特定前缀和 。最后，利用 哈希表存储前缀和首次出现的位置 ，我们就能在 O(1) 时间内判断当前前缀和是否出现过，从而快速计算出可能的最长子数组长度。这是一种“前缀和 + 哈希表”的经典组合应用。