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

April LeetCoding Challenge 16

Description

Count the Number of Good Subarrays

Given an integer array nums and an integer k, return the number of good subarrays of nums.

A subarray arr is good if there are at least k pairs of indices (i, j) such that i < j and arr[i] == arr[j].

A subarray is a contiguous non-empty sequence of elements within an array.

Example 1:

Input: nums = [1,1,1,1,1], k = 10
Output: 1
Explanation: The only good subarray is the array nums itself.

Example 2:

Input: nums = [3,1,4,3,2,2,4], k = 2
Output: 4
Explanation: There are 4 different good subarrays:
- [3,1,4,3,2,2] that has 2 pairs.
- [3,1,4,3,2,2,4] that has 3 pairs.
- [1,4,3,2,2,4] that has 2 pairs.
- [4,3,2,2,4] that has 2 pairs.

Constraints:

• 1 <= nums.length <= 105
• 1 <= nums[i], k <= 109

Solution

class Solution {
public:
  long long countGood(vector<int>& nums, int k) {
    unordered_map<int, int> count;
    int begin = 0;
    long long answer = 0;
    for(int end = 0; end < nums.size(); ++end) {
      k -= count[nums[end]];
      count[nums[end]] += 1;
      while(k <= 0) {
        count[nums[begin]] -= 1;
        k += count[nums[begin]];
        begin += 1;
      }
      answer += begin;
    }
    return answer;
  }
};

// Accepted
// 41/41 cases passed (80 ms)
// Your runtime beats 61.7 % of cpp submissions
// Your memory usage beats 54.61 % of cpp submissions (79.1 MB)