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

April LeetCoding Challenge 24

Description

Count Complete Subarrays in an Array

You are given an array nums consisting of positive integers.

We call a subarray of an array complete if the following condition is satisfied:

• The number of distinct elements in the subarray is equal to the number of distinct elements in the whole array.

Return the number of complete subarrays.

A subarray is a contiguous non-empty part of an array.

Example 1:

Input: nums = [1,3,1,2,2]
Output: 4
Explanation: The complete subarrays are the following: [1,3,1,2], [1,3,1,2,2], [3,1,2] and [3,1,2,2].

Example 2:

Input: nums = [5,5,5,5]
Output: 10
Explanation: The array consists only of the integer 5, so any subarray is complete. The number of subarrays that we can choose is 10.

Constraints:

• 1 <= nums.length <= 1000
• 1 <= nums[i] <= 2000

Solution

class Solution {
public:
  int countCompleteSubarrays(vector<int>& nums) {
    set<int> st(nums.begin(), nums.end());
    int target = st.size();
    map<int, int> count;
    int begin = 0;
    int answer = 0;
    for(int end = 0; end < nums.size(); ++end) {
      count[nums[end]] += 1;
      while(count.size() == target) {
        answer += nums.size() - end;
        count[nums[begin]] -= 1;
        if(!count[nums[begin]]) count.erase(nums[begin]);
        begin += 1;
      }
    }
    return answer;
  }
};

// Accepted
// 1074/1074 cases passed (27 ms)
// Your runtime beats 38.05 % of cpp submissions
// Your memory usage beats 45.93 % of cpp submissions (42 MB)