525. Contiguous Array

문제

https://leetcode.com/problems/contiguous-array/description/

풀이

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

        int sum = 0;
        int max = 0;

        // key는 특정 누적합, values는 누적합이 처음으로 등장한 인덱스
        map.put(0, -1); 

        for(int i = 0; i < nums.length; i++) {
            sum += nums[i] == 0 ? -1 : 1;
            
            // 동일한 누적합이 이전에 존재한다면, 그 사이의 부분 배열은 누적합 0을 만족한다. 
            // - > 0과 1의 개수가 같다. 
            if (map.containsKey(sum)) {
            // 조건을 만족하는 subarray의 길이 (누적합이 처음 등장한 인덱스 + 1 부터 시작하여 현재 인덱스 i까지)
                max = Math.max(max, i - map.get(sum));   
            } else { // 등장한 적이 없다면 map에 새로 저장
                map.put(sum, i);
            }

        }

        return max;
        
    }
}

• 배열에서 가능한 모든 subArray를 탐색하는데서 Sliding Window를 떠올릴 수 있지만,
  다음 인덱스가 0인지 1인지에 따라 lt를 이동시킬지, rt를 이동시킬지가 복잡함
  => 이렇게 Sliding Window를 이용할 수 있으나, 제약조건이 복잡해 포인터를 이동시키기 애매한 경우에는 prefixSum + HashMap 카운팅으로 푸는 것이 훨씬 효율적이다.

• 문제의 핵심은, 현재 index까지의 누적합(홀수+짝수)이 과거에도 존재했다면, 과거의 index와 현재 index사이에 누적합이 0인 (홀수와 짝수의 합이 같은) 부분 배열이 존재한다는 것이다.

• 0인 경우에 -1, 1인 경우에 +1을 해주면 손쉽게 0과 1의 개수를 계산할 수 있음

• subarray의 길이는 i - map.get(sum) + 1 - 1 / map.get(sum)은 sum이 처음 등장한 인덱스

• map.put(0, -1)로 초기화 해주는 이유?

  • 빈 배열의 경우, sum은 0. sum 0이 등장한 인덱스를 -1로 두어야, sum=k(0)인 경우도 포함시킬 수 있다.
  • 안해준다면, sum이 0이 되었을 때, map에는 존재하지 않으므로 유효한 배열로 취급하지 않고 map에 처음 등장한 것처럼 sum을 집어넣게 됨
  • 하지만, 이렇게 초기화를 해준다면, sum이 0일 때, map에도 key가 0인 요소가 존재하므로 정상적으로 부분 배열을 구할 수 있다.
  • i - map.get(sum) +1 - 1, 윗 그림에선 sum = 0인 경우에 1 - (-1) +1 -1 이므로 길이가 2인 [0,1]을 포함시킬 수 있음

=> PrefixSum + HashMap 카운팅 문제의 경우, sum = k 인 경우를 항상 포함시켜야하기 때문에, [] 빈 배열일 때를 고려하여 Map을 초기화 해주는 것이 중요하다.