leetcode525. Contiguous Array

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.

 

문제 : 0,1 로 이루어진 배열이 주어지는데, 연속된 0,1 의 최대 길이를 구해라

 ex ) 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0 이렇게 될경우 최대길이는 6임

 

풀이 

public class Solution {
    public int findMaxLength(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        
        int max = 0;
        int count = 0;
        for(int i=0;i<nums.length;i++){
            if(nums[i] == 0) count --;
            else count++;
            
            /**
            1. count 가 0 이되는 경우는 현재 인덱스까지가 max길이가 된다.
            2. map의 키가 존재하는 뜻은 해당 i 인덱스까지 0과 1이 균등하게 
            이루어져있어 max를 구해야한다.
            
            ex )  [1, 0, 1, 1, 0]
            count  1, 0, 1 ...... >> 동일 키가 발견되었다는 의미는
              해당 인덱스(i=2)와, 앞 count index(i=0)의 사이에 max길이를 구할
              대상이 있다는것이다.
            **/
            
            if(count == 0)
                max = Math.max(max, i+1);
            else if(map.containsKey(count)) 
                max = Math.max(max, i - map.get(count));
            else 
                map.put(count, i);
        }
        
        return max;
    }
}

참조 

https://www.youtube.com/watch?v=9ZyLjjk536U