[Leetcode] 525. Contiguous Array

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

Leetcode - Contiguous Array

문제 유형 : 부분합, 해시

문제 난이도 : Medium

 

문제

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

바이너리 배열 nums가 주어진다. 0과 1의 개수가 같은 부분배열의 최대 길이를 구하시오.

 

풀이

부분합을 이용하여 풀 수 있다.

해시맵을 만들어서 총합-인덱스의 형태로 저장한다.

 

 

배열을 순회하면서, 총합에 0이면 -1을, 1이면 1을 추가한다.

만약 총합이 0이라면, 처음부터 i인덱스까지 조건을 만족하는 부분배열이라는 뜻으로, 최대 길이에 i+1을 대입한다.

만약 다른 총합이 나왔는데, 해시 맵에 없다면, 이 인덱스를 저장시킨다. 그 총합을 가지는 가장 왼쪽이라는 뜻이다.

만약 맵에 같은 총합이 존재한다면, 그 인덱스부터 현재인 i까지 조건을 만족한다는 뜻으로, 최대 길이와 비교하여 갱신시키면 된다.

 

최대 길이를 반환한다.

 

코드

C++

class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        const int n = nums.size();
        unordered_map<int, int> mp;
        int sum = 0;
        int maxLen = 0;

        for(int i = 0; i < n; i++) {
            if(nums[i] == 0) {
                sum--;
            } else {
                sum++;
            }

            if(sum == 0) {
                maxLen = i+1;
                continue;
            }

            if(!mp[sum]) {
                mp[sum] = i+1;
            } else {
                maxLen = max(maxLen, i - mp[sum]+1);
            }
        }

        return maxLen;
    }
};