《剑指 Offer》专项突破版 - 面试题 11 : 0 和 1 个数相同的子数组（C++ 实现）- 前缀和 + 哈希表

题目链接：LCR 011. 连续数组 - 力扣（LeetCode）

题目：

输入一个只包含 0 和 1 的数组，请问如何求 0 和 1 的个数相同的最长连续子数组的长度？例如，在数组 [0, 1, 0] 中有两个子数组包含相同个数的 0 和 1，分别是 [0, 1] 和 [1, 0]，它们的长度都是 2，因此输出 2。

分析：

只要把这个题目稍微变换一下就能重用解决题目 "和为 k 的子数组"?的解题思路。

《剑指 Offer》专项突破版 - 面试题 10 : 和为 k 的子数组（C++ 实现）- 前缀和 + 哈希表-CSDN博客

首先把输入数组中所有的 0 都替换成 -1，那么题目就变成求包含相同数目的 -1 和 1 的最长子数组的长度。在一个只包含 -1 和 1 的子数组中，如果 -1 和 1 的数目相同，那么子数组的所有数字之和就是 0，因此这个题目就变成求数字之和为 0 的最长子数组的长度。

解法类似，可以在扫描数组时累加已经扫描过的数字之和。如果数组中前 i 个数字之和为 x，前 j 个数字（j < i）之和也为 x，那么从第 j + 1 个数字到第 i 个数字的子数组的数字之和为 0，这个和为 0 的子数组的长度是 i - j。

如果扫描到数组的第 i 个数字并累加得到前 i 个数字之和 x，那么就需要知道是否存在一个 j（j < i）使数组中前 j 个数字之和也为 x。可以把数组从第 1 个数字开始到当前扫描的数字累加之和保存到一个哈希表中。由于我们的目标是求出数字之和为 0 的最长子数组的长度，因此还需要知道第 1 次出现累加之和为 x 时扫描到的数字的下标。因此，哈希表的键是从第 1 个数字开始累加到当前扫描到的数字之和，而值是当前扫描的数字的下标。

代码实现：

class Solution {
public:
 ? ?int findMaxLength(vector<int>& nums) {
 ? ? ? ?int n = nums.size();
 ? ? ? ?unordered_map<int, int> sumToIndex;
 ? ? ? ?sumToIndex[0] = -1;
 ? ? ? ?int maxLength = 0;
 ? ? ? ?int sum = 0;
 ? ? ? ?for (int i = 0; i < n; ++i)
 ? ? ?  {
 ? ? ? ? ? ?sum += nums[i] == 0 ? -1 : 1;
 ? ? ? ? ? ?if (sumToIndex.count(sum))
 ? ? ? ? ?  {
 ? ? ? ? ? ? ? ?int j = sumToIndex[sum];
 ? ? ? ? ? ? ? ?if (maxLength < i - j)
 ? ? ? ? ? ? ? ? ? ?maxLength = i - j;
 ? ? ? ? ?  }
 ? ? ? ? ? ?else
 ? ? ? ? ? ? ? ?sumToIndex[sum] = i;
 ? ? ?  }
 ? ? ? ?return maxLength;
 ?  }
};

时间复杂度是 O(n)，空间复杂度也是 O(n)。