525. 连续数组
前言
「力扣题解」系列致力于分享有价值的题目、探讨更优秀的解法。
这是本系列的第 3 篇题解，更多题解关注 Somnia1337@力扣。
基础知识
前缀和，是对数组的每个下标而言，该元素以及之前全部元素的和。
例如，对数组 nums = [1,2,3,4]，可以构造其前缀和数组 preSum = [1,3,6,10]。
由前缀和数组可以快速得到子数组的和，例如，要求 sum(nums[1:3])，即 2+3，只需计算 preSum[2]-preSum[0] = 6-1 = 5。
前缀和是解决子数组相关问题的常用方法。
题目描述
难度：🟡中等
给定一个二进制数组 nums，找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。
示例 1:
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量0和1的最长连续子数组。
示例 2:
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量0和1的最长连续子数组。题意理解
输入：int[]，一个只包含 0、1 的数组。
输出：int，最大的连续子数组长度，该子数组中含有的 0 与 1 的数量相同。
举例：对于 [0,0,1,0,0,1,0]，满足条件的最长子数组为 [1,0,0,1]，返回其长度 4。
解题思路
暴力
你可能最先想到从长到短枚举每个长度为偶数的子数组，返回第一个满足要求的长度。这是一个 的算法，在题目 的数据范围下无疑会超时。
前缀和 + 哈希表
我们要寻找的子数组需满足 1 和 0 数量相同，结合前缀和的知识，我们可以在遇到 1 时将前缀和加 1，遇到 0 时将前缀和减 1。这样一来，如果一个子数组所含的 1 和 0 数量相同，那么它本身求前缀和为 0，因为加 1 的次数与减 1 的次数相同。
以这个数组为例：
求其前缀和：
如果存在两个下标 i<j，且 preSum[j]-preSum[i] == 0，结合用前缀和求子数组和的方法，可以推出 i 和 j 之间的子数组和为 0，也即所含的 1 和 0 数量相同。
例如，i=3 和 j=5 处的 preSum[i] 均为 0，就能推出子数组 nums[4:6] 是满足要求的。
只要枚举所有相等的两个前缀和，其下标作差，差的最大值就是答案。
下标 -1 的特殊处理
观察 nums，发现答案应为 6：
为什么却找不到 preSum[i]==preSum[j] 并且 j-i == 6 的两个下标呢？
这是因为下标从 0 开始，i 最小为 0，所以能找到的子数组都从 1 开始。如果正确答案从 0 开始，这个方法会出问题。
解决方法就是定义前 -1 个元素的前缀和为 0：
这样，可以找到 i=-1，j=5 时 preSum[i]==preSum[j]，5-(-1) 即为答案 6。
优化：哈希表
实现方面，可以用哈希表记录每个不同前缀和所在的最小下标，key 为前缀和，value 为最小下标，时间复杂度从 降至 。
由于先前的前缀和都已经记录在哈希表，只需关注当前的前缀和，可用 int 代替 int[]。
复杂度
- 时间复杂度：。
- 空间复杂度：。
代码
Java
public int findMaxLength(int[] nums) {
Map<Integer, Integer> indices = new HashMap<>(); // 记录每个前缀和的最小下标
indices.put(0, -1); // 定义-1处的前缀和为0
int preSum = 0, ans = 0;
for (int i = 0; i < nums.length; i++) {
preSum += (nums[i] == 1 ? 1 : -1); // 计算前缀和
if (indices.containsKey(preSum)) {
ans = Math.max(i - indices.get(preSum), ans);
}
else {
indices.put(preSum, i); // 第一次遇到，存入下标
}
}
return ans;
}Python
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
indices = {0: -1} # 记录每个前缀和的最小下标，定义-1处的前缀和为0
preSum = 0
ans = 0
for i in range(len(nums)):
preSum += 1 if nums[i] == 1 else -1 # 计算前缀和
if preSum in indices:
ans = max(i - indices[preSum], ans)
else:
indices[preSum] = i # 第一次遇到，存入下标
return ansC++
由 @陈冥雁 提供。
class Solution {
public:
int findMaxLength(vector<int>& nums) {
unordered_map<int, int> indices; // 记录每个前缀和的最小下标
indices[0] = -1; // 定义-1处的前缀和为0
int preSum = 0, ans = 0;
for (int i = 0; i < nums.size(); i++) {
preSum += (nums[i] == 1 ? 1 : -1); // 计算前缀和
if (indices.find(preSum) != indices.end()) {
ans = max(i - indices[preSum], ans);
} else {
indices[preSum] = i; // 第一次遇到，存入下标
}
}
return ans;
}
};相关题目
325. 和等于 k 的最长子数组长度
523. 连续的子数组和
974. 和可被 K 整除的子数组
最后
更多系列「外源推文」&「生活分享」关注公众号：