题目直达

1. 题目描述

描述：

给你一个整数数组 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⁵

• 1 <= nums[i], k <= 10⁹

2. 解答

基本思路：

双指针+记忆化

代码：

func countGood(nums []int, k int) int64 {
	n := len(nums)
	var (
		same int
		cnt  = map[int]int{}
	)
	l, r := 0, 0
	var ans int
	for ; l < n; l++ {
		for same < k && r < n {
			same += cnt[nums[r]]
			cnt[nums[r]]++
			r++
		}
		if same >= k {
			ans += n - r + 1
		}
		cnt[nums[l]]--
		same -= cnt[nums[l]]
	}
	return int64(ans)
}