Leetcode 2537. Count the Number of Good Subarrays

문제

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A subarray arr is good if there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].

A subarray is a contiguous non-empty sequence of elements within an array.

정수 배열 nums와 정수 k가 주어진다.
부분배열이 좋다는것은 내부 index (i, j) 쌍에 대해 $arr[i] == arr[j]$ 인 쌍이 k개 이상 존재한다는 것이다.
주어진 배열에 좋은 부분배열의 갯수를 리턴하시오

---

예시

네, 번역해 드리겠습니다.

입력: nums = [3,1,4,3,2,2,4], k = 2
출력: 4
설명: 다음과 같이 4개의 서로 다른 좋은 부분 배열(good subarrays)이 있습니다:

[3,1,4,3,2,2]는 2개의 쌍(pair)을 가집니다.
[3,1,4,3,2,2,4]는 3개의 쌍(pair)을 가집니다.
[1,4,3,2,2,4]는 2개의 쌍(pair)을 가집니다.
[4,3,2,2,4]는 2개의 쌍(pair)을 가집니다.

---

제한

• $1 <= nums.length <= 10^5$
• $1 <= nums[i], k <= 10^9$

---

풀이

• left를 고정하고 right만 움직여서 좋은 부분배열을 만드는 최소한의 right를 찾는다.
• 그 후 정답에 전체 길이 - right + 1을 더한다.
• 다만 window의 크기는 유동적으로 계산한다.

class Solution:
    def countGood(self, nums: List[int], k: int) -> int:

        N = len(nums)
        hashmap = defaultdict(int)
        full, ans, right = 0, 0, 0

        for left in range(N):
            while right < N and full < k:
                full += hashmap[nums[right]]
                hashmap[nums[right]] += 1
                right += 1

            if full < k:
                return ans

            ans += N - right + 1

            hashmap[nums[left]] -= 1
            full -= hashmap[nums[left]]