Minimum Size Subarray Sum

Q: Какова временная сложность алгоритма поиска минимальной длины подмассива с заданной суммой?

Решение с помощью скользящего окна работает за время O(n) и использует O(1) памяти. Кажется, что внутренний цикл может привести к квадратичной сложности, но left движется только вперёд, поэтому за весь проход он смещается не более чем n раз. Вариант с префиксными суммами работает за O(n log n) , а проверка каждой начальной позиции — за O(n²) .

Q: Зачем изучать решение с префиксными суммами за O(n log n), если существует решение за O(n)?

Интервьюеры часто просят привести его после ответа с O(n) . Это показывает ещё один способ использования положительных значений: префиксные суммы отсортированы, поэтому бинарный поиск находит место, где текущая сумма впервые превышает порог. Этот приём встречается и в других задачах, например при выборе случайного индекса с вероятностью, пропорциональной его весу.

Q: Должна ли сумма элементов подмассива быть в точности равна целевому значению?

Нет. Подходит любая сумма, большая или равная target . При target = 15 сумма элементов окна 9, 3, 7 равна 19, а его длина по-прежнему составляет 3. Если вместо этого нужна точная сумма, окно всё ещё работает для положительных значений: сужайте его, пока сумма больше целевой, и фиксируйте длину только тогда, когда сумма ей равна.

СреднеСкользящее окно Префиксные суммы

+10

Даны положительное целое число target и массив nums положительных целых чисел. Найдите самый короткий подмассив (непрерывную последовательность соседних элементов), сумма которого не меньше target, и верните его длину. Если ни один подмассив не достигает значения target, верните 0.

Функция

minSubArrayLen(target: integer, nums: integer-array) → integer

targetinteger: сумма, которой подмассив должен достичь или превысить
numsinteger-array: массив положительных целых чисел
Возвращаетinteger: длина самого короткого подмассива, сумма которого не меньше целевого значения, или 0, если такого нет

Ограничения

1 ≤ target ≤ 10⁹
1 ≤ nums.length ≤ 2 × 10⁴
1 ≤ nums[i] ≤ 10⁴

Примеры

Ввод: target = 15nums = [4, 2, 9, 3, 7, 1, 5]
Вывод: 3
Пояснение: Ни одна пара соседних чисел не достигает 15: самая большая сумма двух соседних чисел — 9 + 3 = 12. Три числа достигают: 4 + 2 + 9 = 15 и 9 + 3 + 7 = 19, поэтому ответ — 3.

+16 скрытых тестов при отправке

Дополнительный вопрос

Как бы ты решил эту задачу, если бы nums мог также содержать нули и отрицательные числа, при которых скользящее окно больше не работает?

Подсказки

Открывайте по одной. Каждая подсказывает чуть больше.

Открыто 0 из 3

Решение

Все значения положительные, поэтому добавление элементов в подмассив всегда увеличивает его сумму, а удаление всегда уменьшает её. Именно это свойство лежит в основе обоих быстрых решений. Префиксные суммы образуют отсортированный список, поэтому с помощью бинарного поиска можно найти позицию, в которой сумма впервые достигает target. Ещё лучше: оптимальный конец никогда не сдвигается влево, когда начало сдвигается вправо, поэтому одно скользящее окно, которое расширяется справа и сужается слева, находит ответ за один проход.

Продолжайте от каждой начальной точки

Верно, но не успевает на самых больших тестах

Идея

Зафиксируйте начальный индекс и добавляйте значения по одному, двигаясь вправо. Как только текущая сумма достигнет target, вы получите самый короткий подмассив, начинающийся с этого индекса: любой более короткий подмассив заканчивается раньше, и его сумма всё ещё слишком мала. Поэтому зафиксируйте его длину, прекратите расширять подмассив и перейдите к следующему начальному индексу. Ответ — наименьшая длина среди всех начальных индексов.

Для target = 15 и [4, 2, 9, 3, 7, 1, 5] сумма для начального индекса 0 равна 4, 6, 15, и поиск останавливается при длине 3. Для начального индекса 1 суммы равны 2, 11, 14, 21, и поиск останавливается при длине 4. Для начального индекса 2 суммы равны 9, 12, 19, длина снова равна 3. Ни один начальный индекс не даёт результат лучше 3.

Проблема возникает, когда достичь целевой суммы трудно. Если ни один подмассив её не достигает, для каждого начального индекса придётся пройти до конца массива: n(n+1)/2 сложений, то есть 2 × 10^8 при n = 2 × 10^4. Кроме того, для каждого начального индекса суммы вычисляются заново, хотя они уже были рассчитаны для предыдущего.

Алгоритм

Задай best значение 0 — это означает, что пока ничего не найдено.
Для каждого начального индекса задай текущую сумму равной 0.
Перемещай конечный индекс вправо от начального, добавляя nums[end] к сумме.
Когда сумма достигнет target, сохрани end-start+1, если это значение больше best, и прекрати расширять этот отрезок от данного начального индекса.
Верни best.

def minSubArrayLen(target, nums):
    n = len(nums)
    best = 0  # 0 means no subarray found yet
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            if total >= target:
                # The shortest subarray from this start ends here
                if best == 0 or end - start + 1 < best:
                    best = end - start + 1
                break
    return best

Префиксные суммы и бинарный поиск

Идея

Пусть prefix[k] — сумма первых k значений, где prefix[0] = 0. Тогда сумма nums[start..end-1] равна prefix[end] - prefix[start]. Для фиксированного начала нужно найти наименьшее end, для которого prefix[end] ≥ prefix[start] + target.

Все значения положительные, поэтому prefix строго возрастает, и позицию, где оно впервые достигает нужного значения, можно найти бинарным поиском. Для [4, 2, 9, 3, 7, 1, 5] массив prefix равен [0, 4, 6, 15, 18, 25, 26, 31]. Для начала 2 нужно 6 + 15 = 21; первое значение массива prefix, которое не меньше 21, — 25 с индексом 5, поэтому окно nums[2..4] = 9, 3, 7 имеет длину 3.

Если даже prefix[n] меньше требуемого для некоторого начала значения, то для него не подойдет ни один конец, а для любого более позднего начала — тоже, поскольку prefix[start] только увеличивается. Остановитесь на этом. Это n бинарных поисков, время O(n log n) плюс O(n) на массив префиксных сумм. Наибольшее сравниваемое значение — 2 × 10^8 + 10^9, оно помещается в 32-битное целое число.

Алгоритм

Создай массив prefix длины n+1, где prefix[k+1] = prefix[k] + nums[k].
Для каждого начального индекса вычисли need = prefix[start] + target.
Если prefix[n] < need, остановись: для более позднего начального индекса подходящего решения не будет.
Выполни бинарный поиск первой позиции end от start+1 до n, для которой prefix[end] ≥ need, и сохрани end-start, если это пока самая короткая длина.
Верни самую короткую длину или 0, если ни для одного начального индекса подходящего решения не нашлось.

from bisect import bisect_left


def minSubArrayLen(target, nums):
    n = len(nums)
    # prefix[k] is the sum of the first k values; it only grows
    prefix = [0] * (n + 1)
    for i in range(n):
        prefix[i + 1] = prefix[i] + nums[i]
    best = 0
    for start in range(n):
        need = prefix[start] + target
        if prefix[n] < need:
            break  # no window from here on can reach target
        # The first end with prefix[end] >= need closes the shortest window
        end = bisect_left(prefix, need, start + 1)
        if best == 0 or end - start < best:
            best = end - start
    return best

Скользящее окно

Идея

Поддерживайте окно nums[left..right] и его сумму. Сдвигайте right на один шаг за раз и добавляйте новое значение. Пока сумма не меньше target, окно подходит: запишите его длину, затем удалите nums[left] и сдвиньте left вперёд, чтобы проверить, подходит ли ещё более короткое окно.

Почему left можно навсегда сдвинуть дальше? Когда окно nums[left..right] впервые достигает target, сумма меньшего окна nums[left..right-1] этого значения не достигла, потому что на предыдущем шаге цикл уменьшил бы его. Значит, right — это самый ранний конец для этого начала, а любой более поздний конец даст только более длинный подмассив. Для этого начала лучший ответ уже найден. Этот довод работает только для положительных значений: при отрицательном числе сумма более длинного окна позже могла бы оказаться больше.

Для target = 15 и [4, 2, 9, 3, 7, 1, 5]: сумма растёт до 4, 6, 15, поэтому записывается длина 3, а 4 удаляется (11). Добавление 3 даёт 14, добавление 7 — 21: запишите длину 4, удалите 2 (19), запишите длину 3, удалите 9 (10). Добавление 1 и 5 даёт 16: запишите длину 4, удалите 3 (13). Ответ — 3.

Цикл while находится внутри цикла for, но каждый индекс входит в окно один раз и выходит из него один раз, поэтому общий объём работы составляет O(n). Хранятся только три числа, поэтому пространственная сложность — O(1).

Алгоритм

Задай left = 0, total = 0 и best = 0.
Для каждого right добавляй nums[right] к total.
Пока total ≥ target, сохраняй right-left+1, если это значение лучше, чем best, вычитай nums[left] и сдвигай left на один шаг вправо.
Верни best, которое останется равным 0, если сумма так и не достигнет target.

def minSubArrayLen(target, nums):
    best = 0  # 0 means no window found yet
    total = 0  # sum of nums[left .. right]
    left = 0
    for right in range(len(nums)):
        total += nums[right]
        # Shrink while the window still reaches target
        while total >= target:
            if best == 0 or right - left + 1 < best:
                best = right - left + 1
            total -= nums[left]
            left += 1
    return best

Ловушки и крайние случаи

Большинство ошибок возникает на этапе сужения окна и при выборе значения, которое нужно вернуть, если ни одна сумма не достигла target.

Сужение окна с помощью if вместо while. Для target = 12 и [1, 1, 2, 3, 12] добавление 12 даёт сумму 19. Условие if фиксирует длину 5, удаляет одно значение и переходит дальше, поэтому окно [12] длины 1 никогда не измеряется. Цикл продолжает удалять значения, пока сумма остаётся достаточной.
Фиксация длины после удаления nums[left], а не до него. Измерять нужно то окно, сумма которого достигла target.
Сравнение с помощью > вместо ≥. Подмассив, сумма которого равна target, учитывается: для [3, 3, 3] при target = 9 ответ — 3, а не 0.
Возврат значения-заглушки. Если вы задали начальное значение best равным n+1 или бесконечности, замените его на 0, если ни одна сумма не достигла target.
Повторное использование окна для массивов с нулями или отрицательными числами. Этот подход основан на том, что каждое значение положительно; в этой задаче это гарантируется, но в её вариантах — нет.

Частые вопросы4

Какова временная сложность алгоритма поиска минимальной длины подмассива с заданной суммой?

Решение с помощью скользящего окна работает за время O(n) и использует O(1) памяти. Кажется, что внутренний цикл может привести к квадратичной сложности, но left движется только вперёд, поэтому за весь проход он смещается не более чем n раз. Вариант с префиксными суммами работает за O(n log n), а проверка каждой начальной позиции — за O(n²).

Почему для скользящего окна нужны положительные числа?

При уменьшении окна его сумма должна снижаться, а при увеличении — расти, иначе удаление левого элемента может отбросить начало ответа. При отрицательных числах этот порядок нарушается. Обычно эту проблему решают с помощью префиксных сумм и монотонной двусторонней очереди возможных начальных индексов; такой алгоритм по-прежнему работает за O(n).

Зачем изучать решение с префиксными суммами за O(n log n), если существует решение за O(n)?

Интервьюеры часто просят привести его после ответа с O(n). Это показывает ещё один способ использования положительных значений: префиксные суммы отсортированы, поэтому бинарный поиск находит место, где текущая сумма впервые превышает порог. Этот приём встречается и в других задачах, например при выборе случайного индекса с вероятностью, пропорциональной его весу.

Должна ли сумма элементов подмассива быть в точности равна целевому значению?

Нет. Подходит любая сумма, большая или равная target. При target = 15 сумма элементов окна 9, 3, 7 равна 19, а его длина по-прежнему составляет 3. Если вместо этого нужна точная сумма, окно всё ещё работает для положительных значений: сужайте его, пока сумма больше целевой, и фиксируйте длину только тогда, когда сумма ей равна.

Python

def minSubArrayLen(target, nums):
    # Напишите код здесь

Тестовые случаи

Случай 1

Случай 2

Случай 3

Ввод

target = 15
nums = [4, 2, 9, 3, 7, 1, 5]

Ожидается

Minimum Size Subarray Sum

Функция

Ограничения

Примеры

Подсказки

Решение

Продолжайте от каждой начальной точки

Префиксные суммы и бинарный поиск

Скользящее окно

Ловушки и крайние случаи

Частые вопросы4

Похожие задачи