[LeetCode] 525. Contiguous Array - 문제풀이

Description

0,1로만 이루어진 이진 배열에서 0과 1이 같은 개수를 가지는 최대 서브 배열의 길이를 구하는 문제입니다.

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.

Constraints:

• 1 <= nums.length <= 10^5
• nums[i] is either 0 or 1.

Solution 1. Prefix Sum + Hash Table

public int findMaxLength(int[] nums) {

    // 1. prefix Sum + Hash table
    int len = nums.length;
    int max = 0;
    int sum = 0;
    Map<Integer,Integer> map = new HashMap<>(); // sum,index 누적 합계의 인덱스 저장.
    map.put(0,-1);
    for (int i = 0; i < len; i++) {
        sum += nums[i] == 0? -1 : 1;
        if(!map.containsKey(sum)){
            map.put(sum,i);
        }else{
            max = Math.max(max,i- map.get(sum)); // 이미 저장된 합과 같아지는 지점이 있다면 이미 저장된 합의 다음 값부터 현재까지의 값을 더한게 0이라는 뜻.
        }
    }
    return max;
}

Prefix Sum을 HashMap을 이용하여 각 인덱스별 누적 합을 저장해놓고 특정 지점에서 sum이 같아지는 지점이 있다면 이전합의 다음 구간부터 현재구간까지의 합이 0이 되므로 해당 길이를 저장하여 가장 큰 길이를 반환해줍니다.

Solution 2. brute Force

public int findMaxLength(int[] nums) {
    int len = nums.length;
    int max = 0;
    // 2. brute force
    for (int i = 0; i < len; i++) {
        int zero = 0, one = 0;
        for (int j = i; j < len; j++) {
            if(nums[j]==0){
                zero++;
            }else{
                one++;
            }
            if(zero == one){
                max = Math.max(max,j-i+1);
            }
        }
    }
    return max;

}

전체 탐색을 통한 방법입니다. 시간복잡도가 높아 TLE로 통과하지 못합니다.

Reference

Contiguous Array - LeetCode