算法

(哈希表+前缀和) $O(n)$

我们不妨把所有的0都换成-1，然后待求问题的要求的子数组元素和就等于0。
可以用前缀和来做。

Java 代码

class Solution {
    public int findMaxLength(int[] nums) {
        int n = nums.length;
        int max = 0;
        // (presum, first occur position)
        Map<Integer, Integer> map = new HashMap();
        map.put(0, -1); // 一个元素还没取的时候前缀和为0
        for (int i = 0; i < n; ++i) { // 原地更新前缀和
            if (i == 0) nums[i] = nums[i] == 0 ? -1 : nums[i]; // 单独处理i==0
            else {
                if (nums[i] == 0) nums[i] = nums[i - 1] - 1;
                else nums[i] += nums[i - 1];
            }
            if (map.containsKey(nums[i])) { // 如果nums[i]在map里就更新max的值
                max = Math.max(max, i - map.get(nums[i]));
            }
            else map.put(nums[i], i); // 如果不在，就把(nums[i], i)插入哈希表
        }
        return max;
    }
}