Count the Number of Good Subarrays
Uber● MediumFULLTIMEOAProblem statement
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.
Function
countGoodSubarrays(nums: int[], k: int) → intExamples
Example 1
nums = [1,1,1,1,1]k = 10return = 1
The only good subarray is the array nums itself.
Example 2
nums = [3,1,4,3,2,2,4]k = 2return = 4There are 4 different good subarrays:
[3,1,4,3,2,2]that has 2 pairs.[3,1,4,3,2,2,4]that has 3 pairs.[1,4,3,2,2,4]that has 2 pairs.[4,3,2,2,4]that has 2 pairs.
Constraints
1 <= nums.length <= 10^51 <= nums[i], k <= 10^9