[LeetCode] 2348. Number of Zero-Filled Subarrays

- Problem

2348. Number of Zero-Filled Subarrays

정수 배열 nums가 주어질 때, 0으로만 채워진 subarrays의 개수를 반환해야 하는 문제다.
이 때, 부분 배열 subarray는 빈 공간이 없는 연속된 배열이여야 한다.

0으로만 이루어진 배열에서 조건에 부합하는 부분 집합 개수를 세보면 다음과 같다.

• [0]: [0] -> 1개
• [0, 0]: [0], [0], [0, 0] -> 3개
• [0, 0, 0]: [0], [0], [0], [0, 0], [0, 0], [0, 0, 0] -> 6개
• [0, 0, 0, 0]: ... -> 10개

따라서, 배열에서 연속된 0의 개수에 따라 다음과 같은 점화식을 추론해 볼 수 있다.

• 부분 집합의 갯수 = (n * (n + 1)) // 2
  - n: 배열에서 연속된 0의 개수

- 내 풀이 (Two Pointer)

class Solution:
    def zeroFilledSubarray(self, nums: List[int]) -> int:
        answer = 0
        walker = runner = 0

        while walker < len(nums):
            if nums[walker] == 0:
                while runner < len(nums) and nums[runner] == 0:
                    runner += 1
                n = runner - walker # the number of zeros
                answer += (n * (n + 1)) // 2
                walker = runner

            else:
                walker += 1
                runner += 1

        return answer

- 결과

• 시간 복잡도: O(N) (N: nums의 길이)
• 공간 복잡도: O(1)