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 = 10 Output: 1 Explanation: The only good subarray is the array nums itself.
Example 2:
Input: nums = [3,1,4,3,2,2,4], k = 2 Output: 4 Explanation: There 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 <= 1051 <= nums[i], k <= 109class Solution {
public long countGood(int[] nums, int k) {
int n = nums.length, numPairs = 0;
long ans = 0;
Map<Integer, Integer> freq = new HashMap<>();
for(int lt = 0, rt = -1; lt < n; lt++){
while(numPairs<k && rt<n-1){
rt++;
int oldFreq = freq.getOrDefault(nums[rt], 0);
numPairs += oldFreq;
freq.put(nums[rt], oldFreq + 1);
}
if(numPairs>=k)
ans += n - rt;
int oldFreq = freq.get(nums[lt]);
freq.put(nums[lt], oldFreq - 1);
numPairs -= oldFreq - 1;
}
return ans;
}
}