525 Contiguous Array

Leetcode

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

Example 1:

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

Example 2:

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

遍历数组，计算一个 sum ，遇到 1 时 sum+1 ，遇到 0 时 sum-1 ，每次把 sum 的值和下标储存到 map 里，如果一个 sum 在 map 里存在，说明之前得到过这个 sum ，两次同一个 sum 的这一段是一段 0 和 1 个数相等的区间，下标的差值是区间长度。

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