统计好子数组的数目
难度:
标签:
题目描述
Given an integer array nums and an integer k, return the number of good subarrays of nums.
A subarray arr is good if it 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 <= 109
代码结果
运行时间: 127 ms, 内存: 32.1 MB
/*
* 思路：
* 使用 Java Stream 解决这个问题的方式，虽然不像传统方法那样直接，
* 但我们可以使用Stream进行一些中间处理，例如计算前缀和。
*/
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
public class GoodSubarraysStream {
public int countGoodSubarrays(int[] nums, int k) {
Map<Integer, Long> freq = new HashMap<>();
int[] prefixPairs = IntStream.range(0, nums.length)
.map(i -> {
freq.put(nums[i], freq.getOrDefault(nums[i], 0L) + 1);
return freq.get(nums[i]).intValue() - 1;
}).toArray();
int count = 0, pairCount = 0, left = 0;
for (int right = 0; right < nums.length; right++) {
pairCount += prefixPairs[right];
while (pairCount >= k) {
count += nums.length - right;
pairCount -= prefixPairs[left++];
}
}
return count;
}
}解释
方法:
题解中采用了滑动窗口和哈希表的方法来解决问题。遍历数组的每个元素，使用哈希表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)
代码细节讲解
🦆
在题解中，为什么选择哈希表来记录每个元素的出现次数？是否有其他数据结构能达到类似的效果？
▷🦆
题解中说明当count超过或等于k时通过移动左指针来减少count，具体是如何实现count的减少，能否详细解释该逻辑？
▷🦆
题解中提到，'如果count超过或等于k，需要通过移动左指针来减少count，直到count小于k'，这是否意味着只有count等于k时才能形成好子数组？如果count大于k是否还能形成好子数组？
▷