LeetCode (525) - Contiguous Array

하단 Title 클릭 시 해당 문제 페이지로 이동합니다.

- Contiguous Array

• Acceptance: 46.1%
• Difficulty: Medium

문제 설명

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

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

예시 1

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

예시 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의 갯수가 동일한 sub array를 찾는 문제.
• total = 0 에서 값이0이면 -1, 1이면 +1을 더해가며 total = 0 이 되는 경우는 0과 1의 갯수가 같다는 말.
• 진행 중 index = i, total = n 일 때, 이전에 total값 중 n이 나온 경우가 있다면 (index = m), subarray(m, n)은 total = 0 일 것이다.
• 위의 정보를 저장하기 위해 Map을 사용하여 key값으로 total, value 값으로 index를 저장했다.

코드

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findMaxLength(int[] nums) {
        int total = 0, result = 0;
        Map<Integer, Integer> map = new HashMap<>();

        for (int index = 0, length = nums.length; index < length; index++) {
            int number = nums[index] == 1 ? 1 : -1;

            total += number;
            if (total == 0) {
                result = Math.max(result, index + 1);
            }

            if (map.containsKey(total)) {
                result = Math.max(result, index - map.get(total));
            } else {
                map.put(total, index);
            }
        }

        return result;
    }
}