[LeetCode] Subarrays with K Different Integers

992. Subarrays with K Different Integers

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.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
int subarraysWithKDistinct(vector<int>& nums, int k) {
return atMostK(nums, k) - atMostK(nums, k - 1);
}
int atMostK(vector<int>& nums, int k) {
unordered_map<int, int> counter;
int res = 0;
for(int l = 0, r = 0; r < nums.size(); r++) {
if(counter[nums[r]]++ == 0) k--;
while(k < 0) {
if(counter[nums[l]]-- == 1)
k++;
l++;
}
res += r - l;
}
return res;
}
};
Author: Song Hayoung
Link: https://songhayoung.github.io/2022/03/17/PS/LeetCode/subarrays-with-k-different-integers/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.