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.
Example 1
Input
nums = [1,1,1,1,1], k = 10Output
1The only good subarray is the array nums itself.
Example 2
Input
nums = [3,1,4,3,2,2,4], k = 2Output
4There are 4 different good subarrays: [3,1,4,3,2,2], [3,1,4,3,2,2,4], [1,4,3,2,2,4], and [4,3,2,2,4].
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i], k <= 10^9