Description
Given an integer array nums and an integer k, return the number of good subarrays of nums.
A good array is an array where the number of different integers in that array is exactly k.
- For example,
[1,2,3,1,2] has 3 different integers: 1, 2, and 3.
A subarray is a contiguous part of an array.
Example 1:
Input: nums = [1,2,1,2,3], k = 2
Output: 7
Explanation: Subarrays formed with exactly 2 different integers: [1,2], [2,1], [1,2], [2,3], [1,2,1], [2,1,2], [1,2,1,2]
Example 2:
Input: nums = [1,2,1,3,4], k = 3
Output: 3
Explanation: Subarrays formed with exactly 3 different integers: [1,2,1,3], [2,1,3], [1,3,4].
Constraints:
1 <= nums.length <= 2 * 1041 <= nums[i], k <= nums.length
Solutions
Solution 1
PythonJavaC++Go
class Solution:
def subarraysWithKDistinct(self, nums: List[int], k: int) -> int:
def f(k):
pos = [0] * len(nums)
cnt = Counter()
j = 0
for i, x in enumerate(nums):
cnt[x] += 1
while len(cnt) > k:
cnt[nums[j]] -= 1
if cnt[nums[j]] == 0:
cnt.pop(nums[j])
j += 1
pos[i] = j
return pos
return sum(a - b for a, b in zip(f(k - 1), f(k)))(code-box)
class Solution {
public int subarraysWithKDistinct(int[] nums, int k) {
int[] left = f(nums, k);
int[] right = f(nums, k - 1);
int ans = 0;
for (int i = 0; i < nums.length; ++i) {
ans += right[i] - left[i];
}
return ans;
}
private int[] f(int[] nums, int k) {
int n = nums.length;
int[] cnt = new int[n + 1];
int[] pos = new int[n];
int s = 0;
for (int i = 0, j = 0; i < n; ++i) {
if (++cnt[nums[i]] == 1) {
++s;
}
for (; s > k; ++j) {
if (--cnt[nums[j]] == 0) {
--s;
}
}
pos[i] = j;
}
return pos;
}
}(code-box)
class Solution {
public:
int subarraysWithKDistinct(vector<int>& nums, int k) {
vector<int> left = f(nums, k);
vector<int> right = f(nums, k - 1);
int ans = 0;
for (int i = 0; i < nums.size(); ++i) {
ans += right[i] - left[i];
}
return ans;
}
vector<int> f(vector<int>& nums, int k) {
int n = nums.size();
vector<int> pos(n);
int cnt[n + 1];
memset(cnt, 0, sizeof(cnt));
int s = 0;
for (int i = 0, j = 0; i < n; ++i) {
if (++cnt[nums[i]] == 1) {
++s;
}
for (; s > k; ++j) {
if (--cnt[nums[j]] == 0) {
--s;
}
}
pos[i] = j;
}
return pos;
}
};(code-box)
func subarraysWithKDistinct(nums []int, k int) (ans int) {
f := func(k int) []int {
n := len(nums)
pos := make([]int, n)
cnt := make([]int, n+1)
s, j := 0, 0
for i, x := range nums {
cnt[x]++
if cnt[x] == 1 {
s++
}
for ; s > k; j++ {
cnt[nums[j]]--
if cnt[nums[j]] == 0 {
s--
}
}
pos[i] = j
}
return pos
}
left, right := f(k), f(k-1)
for i := range left {
ans += right[i] - left[i]
}
return
}(code-box)
