main.go

// Source: https://leetcode.com/problems/count-complete-subarrays-in-an-array
// Title: Count Complete Subarrays in an Array
// Difficulty: Medium
// Author: Mu Yang <http://muyang.pro>

////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
// 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`
//
////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////////

package main

func countCompleteSubarrays(nums []int) int {
	n := len(nums)

	counter := make(map[int]int)
	neededCount := 0
	for _, num := range nums {
		if _, ok := counter[num]; !ok {
			counter[num] = 0
			neededCount++
		}
	}

	res := 0
	left, right := 0, 0
	for right < n {
		if neededCount != 0 {
			if counter[nums[right]] == 0 {
				neededCount--
			}
			counter[nums[right]]++
			right++
		} else {
			res += (n - right + 1)
			counter[nums[left]]--
			if counter[nums[left]] == 0 {
				neededCount++
			}
			left++
		}
	}

	for neededCount == 0 {
		res++
		counter[nums[left]]--
		if counter[nums[left]] == 0 {
			neededCount++
		}
		left++
	}

	return res
}