目标
给你一个整数数组 nums 和一个整数 k ，请你返回 nums 中 好 子数组的数目。
一个子数组 arr 如果有 至少 k 对下标 (i, j) 满足 i < j 且 arr[i] == arr[j] ，那么称它是一个 好 子数组。
子数组 是原数组中一段连续 非空 的元素序列。
示例 1：
输入：nums = [1,1,1,1,1], k = 10
输出：1
解释：唯一的好子数组是这个数组本身。示例 2：
输入：nums = [3,1,4,3,2,2,4], k = 2
输出：4
解释：总共有 4 个不同的好子数组：
- [3,1,4,3,2,2] 有 2 对。
- [3,1,4,3,2,2,4] 有 3 对。
- [1,4,3,2,2,4] 有 2 对。
- [4,3,2,2,4] 有 2 对。说明：
- 1 <= nums.length <= 10^5
- 1 <= nums[i], k <= 10^9
思路
返回数组 nums 的好子数组个数，好子数组定义为 子数组内至少有 k 对 (i, j) 满足 i < j 且 arr[i] == arr[j]。
可以使用滑动窗口，保证窗口内的子数组中至少包含 k 个合法数对。使用哈希表记录重复元素的个数，同时累加该重复元素新增加的数对个数，如果数对个数大于等于 k，收缩左边界直到数对个数小于 k，在循环中累加结果，子数组 [l, r ~ n - 1] 的个数为 n - r。当然也可以累加 子数组 [0 ~ l - 1, r] 个数为 l，结果是一样的。
代码
/**
* @date 2025-04-16 8:39
*/
public class CountGood2537 {
public long countGood(int[] nums, int k) {
int n = nums.length;
long res = 0;
Map<Integer, Integer> cnt = new HashMap<>();
int l = 0;
int pairCnt = 0;
for (int r = 0; r < n; r++) {
pairCnt += cnt.getOrDefault(nums[r], 0);
cnt.merge(nums[r], 1, Integer::sum);
while (pairCnt >= k){
res += n - r;
cnt.merge(nums[l], -1, Integer::sum);
pairCnt -= cnt.get(nums[l++]);
}
}
return res;
}
}
性能
