难度: Medium
给你一个整数数组 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 <= 1051 <= nums[i], k <= 109运行时间: 127 ms
内存: 32.1 MB
class Solution:
def countGood(self, nums: List[int], k: int) -> int:
res = 0
d = {}
count = 0
left = 0
for x in nums:
if x in d:
count += d[x]
d[x] += 1
else:
d[x] = 1
while count >= k:
d[nums[left]] -= 1
count -= d[nums[left]]
left += 1
res += left
return res
题解中采用了滑动窗口和哈希表的方法来解决问题。遍历数组的每个元素，使用哈希表d来记录每个元素出现的次数。对于每个新元素x，如果x之前出现过，就更新对数计数count。count的更新依据是，如果x在d中，则count增加d[x]，即之前x出现的次数，因为新的x会与之前的每一个x构成一对。随后，d[x]增加1表示x又出现了一次。如果count超过或等于k，需要通过移动左指针来减少count，直到count小于k。对于每个右指针的位置，left的位置表示有多少种子数组结束于当前位置满足条件，即累加left到结果res中。最终，res就是满足条件的好子数组数量。
时间复杂度: O(n)
空间复杂度: O(n)
# 定义类Solution
class Solution:
def countGood(self, nums: List[int], k: int) -> int:
res = 0 # 初始化结果变量
d = {} # 初始化哈希表d，用于记录每个元素的出现次数
count = 0 # 初始化对数计数器
left = 0 # 初始化左指针
for x in nums: # 遍历数组中的每个元素
if x in d: # 如果元素之前出现过
count += d[x] # 更新对数计数器
d[x] += 1 # 更新元素的出现次数
else:
d[x] = 1 # 如果是新元素，记录为出现1次
while count >= k: # 当对数计数器大于等于k时
d[nums[left]] -= 1 # 移动左指针，减少对应元素的出现次数
count -= d[nums[left]] # 更新对数计数器
left += 1 # 左指针右移
res += left # 累加满足条件的子数组数量
return res # 返回结果
在题解中选择哈希表来记录每个元素的出现次数是因为哈希表提供了高效的查找、插入和更新操作，这些操作的平均时间复杂度是O(1)。这对于频繁查询元素出现次数并更新次数的场景非常高效。其他数据结构如平衡树（如AVL树或红黑树）也可以用来记录元素次数，它们支持O(log n)时间复杂度的查找、插入和删除操作，但在本题的场景下，因为操作频繁且需要高效的随机访问速度，使用哈希表更为合适。
在题解中，count表示到目前为止，数组中每个元素与其之前出现的每个相同元素构成的对数。当count超过或等于k时，意味着在右指针当前的位置，子数组中的元素对数过多。为了减少这些对数，我们移动左指针，每移动一次，就将左指针指向的元素的出现次数减1，并相应地减少count。减少的数量为更新后的元素次数，因为每减少一个该元素，就相当于失去了与之前该元素构成对的可能。这样，通过逐步移动左指针，可以逐渐减少count，直到其小于k，此时再停止移动左指针。
不是的。题解中的描述意味着遇到count大于或等于k的情况需要调整子数组的边界以减少count。实际上，只要在调整过程中count的值达到了k，那么这个子数组就是一个好子数组。如果count大于k，说明子数组中的元素对数过多，需要通过调整来减少一些元素，使得对数恰好等于k，才能形成好子数组。因此，好子数组的定义是子数组中的元素对数恰好等于k，而不是大于或等于k。