题目描述

给定一个二进制数组, 找到含有相同数量的 0 和 1 的最长连续子数组（的长度）。

示例 1:

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

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

算法1

(hash) O(n)

首先对原数组做处理，将所有的0都变为-1；这样一来 “含有相同数量的 0 和 1 的连续数组” 就等价为 “元素值总和为0的连续数组”。

其后，从头扫一遍数组，并记录当前的前缀和的值，将该值和对应的下标存入到一个标记数组或哈希表中。若该前缀和的值已出现过（即标记数组或哈希中已存在），则说明标记中的下标到当前扫描的下标的这段数组的总和值是为0的。

打个例子： [ -1，-1，-1，1，-1，1，-1，1，-1，-1，-1，-1 ] 在扫描完到第四个元素时，前缀和为-2 且未记录过，则将值-2和下标3记录起来。当扫描到  [ -1，-1，-1，1，-1，-1，1，1，-1，-1，-1，-1 ]  ， 此时得到的前缀和为-2，且知道标记中有记录过-2，则说明此刻下标到之前记录的下标的这段数组总和为0  [ -1，-1，-1，1，-1，-1，1，1，-1，-1，-1，-1 ]  。

参考文献

Java 代码

public class Solution {

    public int findMaxLength(int[] nums) {
        int n = nums.length;
        if (n == 0) {
            return 0;
        }
        int res = 0,sum = 0;
        Map<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < n; i++) {
            sum += nums[i] != 0 ? 1 : -1;
            if (sum == 0) {
                res = i + 1;
            } else if (map.containsKey(sum)) {
                res = Math.max(res, i - map.get(sum));
            } else {
                map.put(sum, i);
            }
        }

        return res;
    }

}