Today I have done leetcode's March LeetCoding Challenge with cpp.

March LeetCoding Challenge 30

Description

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.

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 * 104
• 1 <= nums[i], k <= nums.length

Solution

class Solution {
  int subarraysWithAtMostKDistinct(const vector<int>& nums, int k) {
    if(!k) return 0;
    int len = nums.size();
    map<int, int> count;
    int result = 0;
    int begin = 0;
    for(int end = 0; end < len; ++end) {
      count[nums[end]] += 1;
      while(begin <= end && count.size() > k) {
        count[nums[begin]] -= 1;
        if(!count[nums[begin]]) count.erase(nums[begin]);
        begin += 1;
      }
      result += (end - begin + 1);
    }
    return result;
  }
public:
  int subarraysWithKDistinct(vector<int>& nums, int k) {
    return subarraysWithAtMostKDistinct(nums, k) - subarraysWithAtMostKDistinct(nums, k - 1);
  }
};