1.题目

给定一个二进制数组 nums , 找到含有相同数量的 0 和 1 的最长连续子数组，并返回该子数组的长度。

示例 1：
输入: nums = [0,1]
输出: 2
说明: [0, 1] 是具有相同数量 0 和 1 的最长连续子数组。

示例 2：
输入: nums = [0,1,0]
输出: 2
说明: [0, 1] (或 [1, 0]) 是具有相同数量 0 和 1 的最长连续子数组。

提示：
1 <= nums.length <= 105
nums[i] 不是 0 就是 1

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/contiguous-array

2.思路

（1）前缀和
常规想法是使用前缀和数组，即 preSum[i] 保存 nums[0…i - 1] 的前缀和，然后再使用两层 for 循环来遍历满足题目条件的子数组，如果符合条件，则更新 res，否则继续遍历。遍历结束后直接返回 res 即可。但是在 LeetCode 上提交时会出现“超出时间限制”的提示！这说明该方法（时间复杂度为 O(n2)）还需优化，具体优化方法见思路 2。

（2）前缀和 & 哈希表
思路参考该LeetCode用户题解。

① 对思路 1 代码中初始化数组 preSum 的操作做一个改动，使用 preSum[i] 来记录 nums[0…i - 1] 中的元素 0 和元素 1 的个数之差：

preSum[i] = preSum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);

显然，我们可以知道:
当 preSum[i] > 0 时，preSum[i] 表示 nums[0…i - 1] 中 1 比 0 多的个数；
当 preSum[i] < 0 时，|preSum[i]| 表示 nums[0…i - 1] 中 1 比 0 少的个数；
当 preSum[i] = 0 时，nums[0…i - 1] 中 0 和 1 的个数相等；

② 定义哈希表 hashMap，用于存放 preSum[i] 及其对应的下标 i；

③ 由于符合题目条件的子数组的长度至少为 2，所以在遍历 preSum 时从下标 2 开始。在遍历过程中，用 hashMap 保存某个子数组中 0、1 元素相差数出现的最小下标，即下面代码中的：

if (!hashMap.containsKey(preSum[i - 2])) {
    hashMap.put(preSum[i - 2], i - 2);
}

④ 同时也判断 preSum[i] 是否存在于 hashMap 中， 如果存在，则设之前出现的下标位置为 preIdx = hashMap.get(preSum[i])，
那么对应的 nums[0…preIdx - 1] 中元素 0 和元素 1 相差的个数为 k，例如 [0, 1, 1, 1]，k = 2，preIdx = 4
同时也可以得知 nums[0…i - 1] 中元素 0 和元素 1 相差的个数也为 k，例如 [0, 1, 1, 1, 0, 1]，k = 2，i = 6
那么此时 nums[preIdx…i - 1] 中元素 0 和元素 1 的个数必相等，即符合条件的子数组为 [0, 1]，对应的长度为 i - preIdx，此时更新 res 即可。

推导的过程也比较简单：

由 preSum[i] = k -> nums[0...i - 1] 中元素 0 和元素 1 相差的个数为 k，
由 preSum[preIdx] = k -> nums[0...preIdx - 1] 中元素 0 和元素 1 相差的个数为 k，且 preIdx < i
由于 nums[0...preIdx - 1] 包含 nums[0...i - 1]，那么显然 nums[0...preIdx - 1] 中元素 0 和元素 1 个数相差为 k 的区间正好
是 nums[0...i - 1]，所以剩余的区间 nums[preIdx...i - 1] 中元素 0 和元素 1 的个数必相等。

3.代码实现（Java）

//思路1————前缀和
class Solution {
    public int findMaxLength(int[] nums) {
        int res = 0;
        int length = nums.length;
        int[] preSum = new int[length + 1];
        for (int i = 1; i < length + 1; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        for (int i = 0; i < length - 1; i++) {
            for (int j = i + 2; j < length + 1; j += 2) {
                int sum_ij = preSum[j] - preSum[i];
                if (sum_ij != 0 && (j - i) / sum_ij == 2 && (j - i) % sum_ij == 0) {
                    res = Math.max(res, j - i);
                }
            }
        }
        return res;
    }
}

//思路2————前缀和 & 哈希表
class Solution {
    public static int findMaxLength(int[] nums) {
        int res = 0;
        int length = nums.length;
        int[] preSum = new int[length + 1];
        for (int i = 1; i < length + 1; i++) {
            preSum[i] = preSum[i - 1] + (nums[i - 1] == 1 ? 1 : -1);
        }
        Map<Integer, Integer> hashMap = new HashMap<>();
        for (int i = 2; i <= length; i++) {
            if (!hashMap.containsKey(preSum[i - 2])) {
                hashMap.put(preSum[i - 2], i - 2);
            }
            if (hashMap.containsKey(preSum[i])) {
                int preIdx = hashMap.get(preSum[i]);
                res = Math.max(res, i - preIdx);
            }
        }
        return res;
    }
}