525. Contiguous Array

525. Contiguous Array

Given a binary array, find the maximum length of a contiguous subarray with equal number of 0 and 1.

Example 1:

Input: [0,1]
Output: 2
Explanation: [0, 1] is the longest contiguous subarray with equal number of 0 and 1.

Example 2:

Input: [0,1,0]
Output: 2
Explanation: [0, 1] (or [1, 0]) is a longest contiguous subarray with equal number of 0 and 1.

Note: The length of the given binary array will not exceed 50,000.

My Solutions:

用一个hashmap储存key = sum，value = 当前index i。先存一个(0, -1)。

用int sum储存当前subarray的总和。用int max储存subarray的最长值。

如果碰到0，在sum里加-1。如果碰到1，在sum里加1。这样只要sum的结果是0，说明0和1的数量相等，此时更新max。

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