862. Shortest Subarray with Sum at Least K

Задача

Даны массив nums и k. Верните длину кратчайшего непустого подмассива с суммой ≥ k (или -1).

Примеры

Пример 1

Input: nums = [1], k = 1
Output: 1

Пример 2

Input: nums = [1,2], k = 4
Output: -1

Пример 3

Input: nums = [2,-1,2], k = 3
Output: 3

Решение

Решение

/**
 * Сложность:
 * - Time: O(N) 
 *   Пояснение: Каждый индекс 0..N добавляется в deque ровно один раз (dq.push) 
 *   и удаляется из deque (через head++ или pop) тоже максимум один раз. 
 *   Внутри циклов while операции амортизируются до константы.
 * 
 * - Space: O(N)
 *   Пояснение: Храним массив префиксных сумм длины N+1 и deque, 
 *   который в худшем случае может содержать все N+1 индексов (для монотонно возрастающей последовательности).
 */
function shortestSubarray(numbers, targetSum) {
    const length = numbers.length;
 
    // Создаем массив префиксных сумм
    // prefixSums[0] = 0 (пустой подмассив)
    // prefixSums[index] = сумма всех элементов numbers[0..index-1]
    const prefixSums = new Array(length + 1);
    prefixSums[0] = 0;
 
    for (let index = 0; index < length; index++) {
        prefixSums[index + 1] = prefixSums[index] + numbers[index];
    }
 
    // Дек для хранения индексов префиксных сумм
    // Реализован через обычный массив + указатель на начало
    const dequeIndices = [];
    let dequeHeadIndex = 0; // Указатель на текущее начало дека
 
    let shortestLength = Infinity;
 
    // Проходим по всем префиксным суммам (включая нулевую)
    for (let rightPrefixIndex = 0; rightPrefixIndex <= length; rightPrefixIndex++) {
        const currentPrefixSum = prefixSums[rightPrefixIndex];
 
        // Шаг 1: Ищем валидные подмассивы и пытаемся уменьшить их длину
        // Удаляем индексы с начала дека, пока сумма подмассива >= targetSum
        while (dequeHeadIndex < dequeIndices.length) {
            const leftPrefixIndex = dequeIndices[dequeHeadIndex];
 
            // Сумма подмассива [leftPrefixIndex, rightPrefixIndex)
            const subarraySum = currentPrefixSum - prefixSums[leftPrefixIndex];
 
            if (subarraySum >= targetSum) {
                // Нашли валидный подмассив, обновляем минимальную длину
                const windowLength = rightPrefixIndex - leftPrefixIndex;
                shortestLength = Math.min(shortestLength, windowLength);
 
                // Удаляем leftPrefixIndex из дека, так как для будущих
                // rightPrefixIndex расстояние будет только больше
                dequeHeadIndex++;
            } else {
                // Сумма слишком мала, дальше удалять нельзя
                break;
            }
        }
 
        // Шаг 2: Поддерживаем монотонность дека (возрастающие префиксные суммы)
        // Удаляем с конца индексы, чьи префиксные суммы >= текущей
        while (dequeHeadIndex < dequeIndices.length) {
            const lastPrefixIndexInDeque = dequeIndices[dequeIndices.length - 1];
 
            // Если префиксная сумма в конце дека >= текущей, удаляем её
            // Причина: текущий индекс более выгоден (меньшая сумма + правее)
            if (prefixSums[lastPrefixIndexInDeque] >= currentPrefixSum) {
                dequeIndices.pop();
            } else {
                break;
            }
        }
 
        // Шаг 3: Добавляем текущий индекс в конец дека
        dequeIndices.push(rightPrefixIndex);
    }
 
    // Если не нашли валидный подмассив, возвращаем -1
    return shortestLength === Infinity ? -1 : shortestLength;
}

Решение 1 (с изменением deque для простого восприятия)

function shortestSubarray(nums, k) {
    const n = nums.length;
 
    // 1. Создаем массив префиксных сумм
    const prefixSums = new Array(n + 1);
    prefixSums[0] = 0;
    for (let i = 0; i < n; i++) {
        prefixSums[i + 1] = prefixSums[i] + nums[i];
    }
 
    // Дек хранит индексы. Мы будем реально удалять элементы из него.
    const dequeIndices = [];
 
    let minLength = Infinity;
 
    // Проходим по всем префиксным суммам
    for (let i = 0; i < prefixSums.length; i++) {
        const currentPrefixSum = prefixSums[i];
 
        // ШАГ 1: Проверяем начало дека (самые старые индексы)
        // Если разница между текущей суммой и началом дека >= k,
        // значит мы нашли валидный подмассив.
        while (dequeIndices.length > 0) {
            const firstIndex = dequeIndices[0]; // Берем первый элемент
            const sum = currentPrefixSum - prefixSums[firstIndex];
 
            if (sum >= k) {
                // Окно подходит! Обновляем минимальную длину
                minLength = Math.min(minLength, i - firstIndex);
 
                // Удаляем первый индекс навсегда.
                // Почему? Потому что если мы пойдем дальше (i увеличится),
                // длина окна с этим firstIndex будет только расти. 
                // Короче, чем сейчас, с этим стартом мы уже не найдем.
                dequeIndices.shift(); 
            } else {
                // Если даже с самым маленьким (дальним) индексом сумма < k,
                // то проверять остальные нет смысла — они дадут еще меньшую сумму.
                break;
            }
        }
 
        // ШАГ 2: Поддерживаем монотонность (удаляем с конца)
        // Если последний индекс в деке имеет префиксную сумму БОЛЬШЕ текущей,
        // он нам не нужен. Текущий индекс 'i' дает меньшую сумму и находится правее.
        while (dequeIndices.length > 0) {
            const lastIndex = dequeIndices[dequeIndices.length - 1];
 
            if (prefixSums[lastIndex] >= currentPrefixSum) {
                dequeIndices.pop(); // Выкидываем "плохого" кандидата с конца
            } else {
                break;
            }
        }
 
        // ШАГ 3: Добавляем текущий индекс в дек
        dequeIndices.push(i);
    }
 
    return minLength === Infinity ? -1 : minLength;
}