[Leetcode] 525. 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.

Constraints:

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

 

풀이

이 문제는 hashmap을 사용해 

1. 1의 갯수와 0의 갯수가 for loop을 지나면서 같게 되는 때 찾고

2. 같게 될 때의 index range의 크기 (len)를 구해, 그 len의 maximum을 찾으면 된다.

 

0을 -1로 생각해서 문제를 보면 쉽게 풀 수 있는데

[-1,1] 의 -1의 갯수와 1의 갯수가 같게 되는 때는 sum이 0이 되는 때이다.

 

그럼.    [-1, 1, 1, 1, 1, -1, -1, -1] 은 여러번 0이 나오게 되는데 

sum = [-1, 0, 1, 2, 3, 2, 1, 0] 중 0이 나올때 len가 가장 큰 것을 찾으면 된다.

 

하지만 꼭 sum이 0일 때 항상 maxlen을 찾는건 아니다.

 

만약 위의 예시에서 마지막 -1이 없다면,

nums=[-1, 1, 1, 1, 1, -1, -1]

sum = [-1, 0, 1, 2, 3, 2, 1] sum이 1 일때 maxlen을 찾을 수 있다.

위처럼 같은 sum이 다시 나온다는 건, +1과 -1이 같은 수만큼 add 되었다는 뜻이므로

같은 sum이 다시 나온다는 건 (have seen), -1의 갯수와 1의 갯수가 같다는 의미다.

 

이 이해를 바탕으로 문제로 돌아가자. 

1. 1의 갯수와 0의 갯수가 for loop을 지나면서 같게 되는 때 (같은 sum이 다시 나올 때(have seen)) 찾고

2. 같게 될 때의 index range의 크기 (len)를 구해, 그 maxlen을 찾으면 된다.

 

hashmap의 index를 prefixsum (sum)으로 하고 output를 index of array 로 설정하고

모든 hashmap을 -2 (아직 같은 sum이 나오지 않음; haven't seen)로 memset 해준다..

1. 배열을 순차적으로 탐색하면서 1이면 더하고 0이면 1을 뺀다.
2. prefixsum을 처음 본다면 (-2), 더한 값(prefixsum)에 현재 인덱스를 저장
3. prefixsum을 본적 있다면 (!-2),
4. 현재 인덱스에서 해당 인덱스까지의 합을 빼준 값 (len)를 찾고 maxlen를 갱신

 

 

코드

int findMaxLength(int* nums, int numsSize) {
    int* hashmap = (int*)malloc((2*numsSize+1)*sizeof(int));
                                                            // stores the index of prefixsum, key is a prefixsum = sum from index 0
                                                            // when nums[i]=1, prefixsum++ ; when nums[i]=0, prefixsum--
    for(int i=0; i<2*numsSize+1; i++) {
        hashmap[i] = -2; // -2 : haven't seen
    }

    int maxlen = 0;
    int prefixsum = numsSize; // avoid negative index of array (prefixsum)
    hashmap[numsSize] = -1; // when #ones == #zeros

    for(int i=0; i<numsSize; i++) {
        prefixsum += (nums[i] == 1)? 1 : -1; // if 1, add 1 to prefixsum; else, -1.
        
        if(hashmap[prefixsum] == -2) { // haven't seen
            hashmap[prefixsum] = i;
        } else { // have seen; when #ones == #zeros
            int len = i - hashmap[prefixsum];
            maxlen = (len > maxlen)? len : maxlen;
        }
    }
    return maxlen;
}