[LeetCode] 525 | Contigous Array | Python

---

문제 링크: https://leetcode.com/problems/contiguous-array/

---

문제

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.

---

내 풀이

Subarray 내의 0과 1의 수가 같은, 가장 긴 subarray를 찾는 문제다.

이는 현재까지의 합을 dictionary로 저장해 쉽게 구할 수 있다.

 

처음 array가 들어왔을 때, 초기화 상태다.

 

첫번째 수는 0이므로, count는 -1이 되고, -1은 cur_sum에 존재하지 않기 때문에 새로 추가된다.

이와 같은 과정을 반복하면 다음과 같이 된다.

 

 

 

count가 cur_sum에 존재할 때마다 ans = max(ans, idx - cur_sum[count])를 실행하는 이유는 다음과 같다.

idx 1까지의 count가 3이고, idx 10까지의 count가 3이면, 그 안의 0과 1의 갯수는 동일하기 때문이다.

---

코드

class Solution:
    def findMaxLength(self, nums: List[int]) -> int:
        ans = 0
        count = 0
        cur_sum = {0: -1}
        
        for idx, num in enumerate(nums):
            if num:
                count += 1
            else:
                count -= 1
            
            if count in cur_sum:
                ans = max(ans, idx - cur_sum[count])
            else:
                cur_sum[count] = idx
                
        return ans