Задача: 659. Split Array into Consecutive Subsequences
Сложность: medium

Вам дан отсортированный в неубывающем порядке массив целых чисел nums.

Определите, можно ли разделить nums на одну или несколько подпоследовательностей так, чтобы выполнялись оба следующих условия:

Каждая подпоследовательность является последовательностью последовательных возрастающих чисел (то есть каждое целое число на 1 больше предыдущего).
Все подпоследовательности имеют длину 3 или более.
Верните true, если можно разделить nums согласно вышеуказанным условиям, или false в противном случае.

Подпоследовательность массива — это новый массив, который формируется из исходного массива путем удаления некоторых (может быть, ни одного) элементов без нарушения относительных позиций оставшихся элементов. (например, [1,3,5] является подпоследовательностью [1,2,3,4,5], тогда как [1,3,2] не является).

Пример:

Input: nums = [1,2,3,3,4,5]
Output: true

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

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

2⃣Создание подпоследовательностей:
Создайте хеш-таблицу для отслеживания количества подпоследовательностей, которые могут быть продолжены для каждого элемента.
Пройдите по каждому элементу в массиве и выполните следующие действия:
Если элемент можно добавить к существующей подпоследовательности (проверяя хеш-таблицу подпоследовательностей), добавьте его и обновите хеш-таблицу.
Если элемент нельзя добавить к существующей подпоследовательности, начните новую последовательность длиной 3 или более элементов.
Если ни одно из условий не выполнено, верните false.

3⃣Проверка результата:
Верните true, если все элементы успешно распределены по подпоследовательностям.

😎 Решение:

class Solution {
    function isPossible($nums) {
        $freq = array_count_values($nums);
        $need = [];
        
        foreach ($nums as $num) {
            if ($freq[$num] == 0) continue;

            if (isset($need[$num]) && $need[$num] > 0) {
                $need[$num]--;
                $need[$num + 1] = isset($need[$num + 1]) ? $need[$num + 1] + 1 : 1;
            } elseif (isset($freq[$num + 1]) && $freq[$num + 1] > 0 && isset($freq[$num + 2]) && $freq[$num + 2] > 0) {
                $freq[$num + 1]--;
                $freq[$num + 2]--;
                $need[$num + 3] = isset($need[$num + 3]) ? $need[$num + 3] + 1 : 1;
            } else {
                return false;
            }
            $freq[$num]--;
        }
        
        return true;
    }
}

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