[Leetcode] Problem 525 - Contiguous Array

Posted on | In ,

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

Example

No.1

Input: [0,1]

Output: 2

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

No.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.

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int findMaxLength(int[] nums) {
    int max = 0;
    int sum = 0;
    Map<Integer, Integer> index = new HashMap<>();

    for (int i = 0; i < nums.length; i++) {
        sum += nums[i] == 1 ? 1 : -1;

        if (sum == 0)
            max = i + 1;
        else if (!index.containsKey(sum))
            index.put(sum, i);
        else
            max = Math.max(max, i - index.get(sum));
    }

    return max;
}