class Solution {
public:
int subarraysWithKDistinct(vector<int>& nums, int k) {
}
};
992. K 个不同整数的子数组
给定一个正整数数组 nums和一个整数 k ，返回 num 中 「好子数组」 的数目。
如果 nums 的某个子数组中不同整数的个数恰好为 k，则称 nums 的这个连续、不一定不同的子数组为 「好子数组 」。
[1,2,3,1,2] 中有 3 个不同的整数：1，2，以及 3。子数组 是数组的 连续 部分。
示例 1：
输入：nums = [1,2,1,2,3], k = 2 输出：7 解释：恰好由 2 个不同整数组成的子数组：[1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2].
示例 2：
输入：nums = [1,2,1,3,4], k = 3 输出：3 解释：恰好由 3 个不同整数组成的子数组：[1,2,1,3], [2,1,3], [1,3,4].
提示：
1 <= nums.length <= 2 * 1041 <= nums[i], k <= nums.length原站题解
python3 解法, 执行用时: 612 ms, 内存消耗: 19.1 MB, 提交时间: 2023-06-01 10:26:35
class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
return self.atMostK(nums, k) - self.atMostK(nums, k - 1)
def atMostK(self, A: List[int], K: int):
N = len(A)
left, right = 0, 0
counter = collections.Counter()
distinct = 0
res = 0
while right < N:
if counter[A[right]] == 0:
distinct += 1
counter[A[right]] += 1
while distinct > K:
counter[A[left]] -= 1
if counter[A[left]] == 0:
distinct -= 1
left += 1
res += right - left + 1
print(left, right, res)
right += 1
return res
golang 解法, 执行用时: 32 ms, 内存消耗: 6.6 MB, 提交时间: 2023-06-01 10:25:01
func subarraysWithKDistinct(nums []int, k int) (ans int) {
n := len(nums)
num1 := make([]int, n+1)
num2 := make([]int, n+1)
var tot1, tot2, left1, left2 int
for _, v := range nums {
if num1[v] == 0 {
tot1++
}
num1[v]++
if num2[v] == 0 {
tot2++
}
num2[v]++
for tot1 > k {
num1[nums[left1]]--
if num1[nums[left1]] == 0 {
tot1--
}
left1++
}
for tot2 > k-1 {
num2[nums[left2]]--
if num2[nums[left2]] == 0 {
tot2--
}
left2++
}
ans += left2 - left1
}
return ans
}
python3 解法, 执行用时: 264 ms, 内存消耗: 19.8 MB, 提交时间: 2023-06-01 10:24:41
class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
n = len(nums)
num1, num2 = collections.Counter(), collections.Counter()
tot1 = tot2 = 0
left1 = left2 = right = 0
ret = 0
for right, num in enumerate(nums):
if num1[num] == 0:
tot1 += 1
num1[num] += 1
if num2[num] == 0:
tot2 += 1
num2[num] += 1
while tot1 > k:
num1[nums[left1]] -= 1
if num1[nums[left1]] == 0:
tot1 -= 1
left1 += 1
while tot2 > k - 1:
num2[nums[left2]] -= 1
if num2[nums[left2]] == 0:
tot2 -= 1
left2 += 1
ret += left2 - left1
return ret
javascript 解法, 执行用时: 84 ms, 内存消耗: 48.2 MB, 提交时间: 2023-06-01 10:24:28
/**
* @param {number[]} nums
* @param {number} k
* @return {number}
*/
var subarraysWithKDistinct = function(nums, k) {
const n = nums.length;
const num1 = new Array(n + 1).fill(0);
const num2 = new Array(n + 1).fill(0);
let tot1 = 0, tot2 = 0;
let left1 = 0, left2 = 0, right = 0;
let ret = 0;
while (right < n) {
if (num1[nums[right]] == 0) {
tot1++;
}
num1[nums[right]]++;
if (num2[nums[right]] == 0) {
tot2++;
}
num2[nums[right]]++;
while (tot1 > k) {
num1[nums[left1]]--;
if (num1[nums[left1]] == 0) {
tot1--;
}
left1++;
}
while (tot2 > k - 1) {
num2[nums[left2]]--;
if (num2[nums[left2]] == 0) {
tot2--;
}
left2++;
}
ret += left2 - left1;
right++;
}
return ret;
};
java 解法, 执行用时: 3 ms, 内存消耗: 45 MB, 提交时间: 2023-06-01 10:24:13
// 滑动窗口
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
int n = nums.length;
int[] num1 = new int[n + 1];
int[] num2 = new int[n + 1];
int tot1 = 0, tot2 = 0;
int left1 = 0, left2 = 0, right = 0;
int ret = 0;
while (right < n) {
if (num1[nums[right]] == 0) {
tot1++;
}
num1[nums[right]]++;
if (num2[nums[right]] == 0) {
tot2++;
}
num2[nums[right]]++;
while (tot1 > k) {
num1[nums[left1]]--;
if (num1[nums[left1]] == 0) {
tot1--;
}
left1++;
}
while (tot2 > k - 1) {
num2[nums[left2]]--;
if (num2[nums[left2]] == 0) {
tot2--;
}
left2++;
}
ret += left2 - left1;
right++;
}
return ret;
}
}
java 解法, 执行用时: 4 ms, 内存消耗: 45 MB, 提交时间: 2023-06-01 10:23:47
// 双指针
public class Solution {
public int subarraysWithKDistinct(int[] A, int K) {
return atMostKDistinct(A, K) - atMostKDistinct(A, K - 1);
}
/**
* @param A
* @param K
* @return 最多包含 K 个不同整数的子区间的个数
*/
private int atMostKDistinct(int[] A, int K) {
int len = A.length;
int[] freq = new int[len + 1];
int left = 0;
int right = 0;
// [left, right) 里不同整数的个数
int count = 0;
int res = 0;
// [left, right) 包含不同整数的个数小于等于 K
while (right < len) {
if (freq[A[right]] == 0) {
count++;
}
freq[A[right]]++;
right++;
while (count > K) {
freq[A[left]]--;
if (freq[A[left]] == 0) {
count--;
}
left++;
}
// [left, right) 区间的长度就是对结果的贡献
res += right - left;
}
return res;
}
}