leetcode 1248. Count Number of Nice Subarrays

문제 

풀이

투포인터를 활용할 수 있었지만, 누적 합으로 더 쉽게 풀 수 있는 문제였다.

배열에서 홀수 개수가 정확히 k개인 연속 부분 배열(subarray) 개수를 구해야 하는 문제다.

 

1. prefix_count라는 딕셔너리를 만들어 누적된 홀수 개수를 기록했다.
   • 처음에 prefix_count[0] = 1로 초기화해서, odd_count - k == 0인 경우도 처리할 수 있도록 했다.
2. 배열을 순회하면서 odd_count를 업데이트했다.
   • 현재 숫자가 홀수면 odd_count += 1을 해준다.
   • odd_count - k가 존재하는 경우, 그 개수만큼 k개의 홀수를 포함하는 부분 배열이 있다는 뜻이므로 result에 더해준다.
3. prefix_count를 갱신해 나갔다.
   • 현재 odd_count 값을 prefix_count에 추가해서 이후 계산에 활용할 수 있도록 했다.

O(N)으로 문제를 해결할 수 있었다.

 

 

코드

from collections import defaultdict
class Solution:
    def numberOfSubarrays(self, nums: List[int], k: int) -> int:
        prefix_count = defaultdict(int)
        prefix_count[0] = 1  
        
        odd_count = 0
        result = 0

        for num in nums:
            if num % 2 != 0:
                odd_count +=1
            result += prefix_count[odd_count-k]
            prefix_count[odd_count] += 1

        return result