Задача: 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⃣Возврат результата:
Верните общее количество "хороших" подмассивов.

😎 Решение:

class Solution {
    function countGoodSubarrays($nums, $k) {
        $count = 0;
        $left = 0;
        $right = 0;
        $distinctCount = 0;
        $freq = [];
        
        while ($right < count($nums)) {
            if (!isset($freq[$nums[$right]])) {
                $freq[$nums[$right]] = 0;
            }
            $freq[$nums[$right]]++;
            if ($freq[$nums[$right]] == 1) {
                $distinctCount++;
            }
            $right++;
            
            while ($distinctCount > $k) {
                $freq[$nums[$left]]--;
                if ($freq[$nums[$left]] == 0) {
                    $distinctCount--;
                }
                $left++;
            }
            
            if ($distinctCount == $k) {
                $count++;
            }
        }
        
        return $count;
    }
}

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