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 <= 105
1 <= nums[i], k <= 109
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)
}
评论