Sponsored
Sponsored
The two-pointer technique can be employed with a sliding window approach to count subarrays with exactly k distinct numbers. The key idea is to maintain a window using two pointers that expand and shrink to keep track of the number of unique integers.
For this, we use the number of subarrays with at most k distinct numbers and at most (k-1) distinct numbers. The difference between these two values gives the number of subarrays with exactly k distinct integers.
Time Complexity: O(n), where n is the length of the array, because each element is added and removed from the data structure at most twice.
Space Complexity: O(n), due to the storage used by the hash map.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int SubarraysWithKDistinct(int[] nums, int k) {
6 return AtMost(nums, k) - AtMost(nums, k - 1);
7 }
8
9 private int AtMost(int[] nums, int k) {
10 Dictionary<int, int> count = new Dictionary<int, int>();
11 int left = 0, res = 0;
12 for (int right = 0; right < nums.Length; right++) {
13 if (!count.ContainsKey(nums[right])) {
14 count[nums[right]] = 0;
15 }
16 count[nums[right]]++;
17 if (count[nums[right]] == 1) k--;
18 while (k < 0) {
19 count[nums[left]]--;
20 if (count[nums[left]] == 0) {
21 count.Remove(nums[left]);
22 k++;
23 }
24 left++;
25 }
26 res += right - left + 1;
27 }
28 return res;
29 }
30}The C# approach leverages dictionaries to keep track of element counts within a window. The functions calculate subarrays with at most k distinct integers and determine the exact count of subarrays with k distinct by calculating the difference.