Задача: 992. Subarrays with K Different Integers
Сложность: hard

Дан целочисленный массив nums и целое число k, верните количество "хороших" подмассивов в nums.

"Хороший" массив - это массив, в котором количество различных целых чисел равно k.

Например, в массиве [1,2,3,1,2] есть 3 различных целых числа: 1, 2 и 3.
Подмассив - это непрерывная часть массива.

Пример:

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]

👨‍💻 Алгоритм:

1⃣Подсчет подмассивов с различными элементами:
Используйте два указателя для определения границ текущего подмассива.
Используйте хэш-таблицу для подсчета количества различных элементов в текущем подмассиве.
Перемещайте правый указатель для расширения подмассива и добавления новых элементов.

2⃣Проверка условий:
Как только количество различных элементов достигнет k, перемещайте левый указатель, чтобы уменьшить размер подмассива и попытаться найти все возможные "хорошие" подмассивы.
Подсчитывайте количество подмассивов, удовлетворяющих условию.

3⃣Возврат результата:
Верните общее количество "хороших" подмассивов.

😎 Решение:

var countGoodSubarrays = function(nums, k) {
    let count = 0;
    let left = 0;
    let right = 0;
    let distinctCount = 0;
    const freq = new Map();
    
    while (right < nums.length) {
        freq.set(nums[right], (freq.get(nums[right]) || 0) + 1);
        if (freq.get(nums[right]) === 1) {
            distinctCount++;
        }
        right++;
        
        while (distinctCount > k) {
            freq.set(nums[left], freq.get(nums[left]) - 1);
            if (freq.get(nums[left]) === 0) {
                distinctCount--;
            }
            left++;
        }
        
        if (distinctCount === k) {
            count++;
        }
    }
    
    return count;
};

Ставь 👍 и забирай 📚 Базу знаний