Longest Subarray with Sum K

+10

Даны целые числа nums и целевое значение k. Верните длину самого длинного подмассива, сумма элементов которого в точности равна k. Подмассив — это последовательность из нескольких подряд идущих элементов длиной не менее одного. Некоторые значения могут быть равны нулю или быть меньше нуля. Если ни один подмассив не даёт в сумме k, верните 0.

Функция

longestSubarrayWithSumK(nums: integer-array, k: integer) → integer

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

Ограничения

1 ≤ nums.length ≤ 2 × 10⁴
-10⁴ ≤ nums[i] ≤ 10⁴
-10⁹ ≤ k ≤ 10⁹
Каждая префиксная сумма находится в диапазоне от -2 × 10⁸ до 2 × 10⁸, поэтому 32-разрядных целых чисел достаточно.
Верни 0, если сумма элементов ни одного подмассива не равна k.

Примеры

Ввод: nums = [2, -1, 3, 1, -4, 2, 3]k = 5
Вывод: 5
Пояснение: Три последовательности в сумме дают 5: [2, 3] в конце, [2, -1, 3, 1] в начале и [3, 1, -4, 2, 3] с индекса 2 по индекс 6. Последняя — самая длинная, в ней 5 элементов.

Ввод: nums = [4, 1, 1, 2, -1, 1]k = 3
Вывод: 4
Пояснение: [1, 1, 2, -1] с индексами от 1 до 4 и [1, 2, -1, 1] с индексами от 2 до 5 в сумме дают 3 и содержат по 4 элемента. Ты возвращаешь длину, поэтому ничья не имеет значения.

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

Как найти самый длинный подмассив, сумма которого не превышает k, при этом отрицательные значения по-прежнему допускаются?

Подсказки

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

Открыто 0 из 3

Решение

Накопительные суммы превращают сумму любого подмассива в одно вычитание: элементы после индекса s и до индекса i включительно дают сумму prefix[i] - prefix[s]. Запомни первый индекс, на котором встречается каждая сумма, и за один проход найди самое длинное совпадение, заканчивающееся в каждой позиции.

Увеличивайте каждый подмассив, начиная с каждого начального индекса

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

Идея

Начиная с каждого элемента, двигайтесь вправо и добавляйте каждый элемент к текущей сумме. Когда сумма равна k, запишите длину. Каждый подмассив — это одна пара начального и конечного индексов, поэтому ни один не будет пропущен. Продолжайте расширять подмассив, даже когда сумма превысит k: начиная с индекса 2 в первом примере суммы равны 3, 4, 0, 2, 5, и именно из-за -4 последняя достигает 5.

Всего примерно n²/2 пар: 2 × 10^8 сложений при n = 2 × 10^4.

Алгоритм

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

def longestSubarrayWithSumK(nums, k):
    n = len(nums)
    best = 0
    for start in range(n):
        total = 0
        for end in range(start, n):
            total += nums[end]
            # A match may come after the total has passed k, so never stop early
            if total == k and end - start + 1 > best:
                best = end - start + 1
    return best

Префиксные суммы с первым индексом каждой суммы

Идея

Последовательность, заканчивающаяся на индексе i, имеет сумму k тогда и только тогда, когда какая-то более ранняя накопленная сумма равна prefix - k. Если подходят несколько более ранних накопленных сумм, самая ранняя из них начинает самую длинную последовательность, поэтому в map каждая сумма сохраняется только при первом появлении. Более поздняя копия могла бы начать только более короткую последовательность. Инициализируй map суммой 0 на индексе -1, чтобы совпадение, начинающееся на индексе 0, давало длину i + 1.

В первом примере накопленные суммы равны 2, 1, 4, 5, 1, 3, 6. На индексе 6 значение 6 - 5 = 1 впервые появилось на индексе 1, что даёт длину 5. Сумма 1 снова появляется на индексе 4, и именно сохранение индекса 1 позволяет найти эту последовательность.

Один поиск на элемент даёт время O(n), а map хранит не более n + 1 сумм.

Алгоритм

Создай карту first, содержащую сумму 0 по индексу -1, и установи prefix и best в 0.
Для каждого индекса i прибавь nums[i] к prefix.
Если prefix - k уже есть в карте по индексу start, установи best равным большему из best и i - start.
Если prefix ещё нет в карте, сохрани его с индексом i.
Верни best.

def longestSubarrayWithSumK(nums, k):
    # first[p] is the index where the prefix sum p first appears; the empty prefix sits at -1
    first = {0: -1}
    prefix = 0
    best = 0
    for i, num in enumerate(nums):
        prefix += num
        # The earliest prefix equal to prefix - k starts the longest match that ends at i
        start = first.get(prefix - k)
        if start is not None and i - start > best:
            best = i - start
        # Keep the first index only: a later one could only start a shorter subarray
        if prefix not in first:
            first[prefix] = i
    return best

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

Перезапись сохранённого индекса при каждом повторении суммы сохраняет последнее начало и позволяет найти более короткое совпадение. В первом примере возвращается 4 вместо 5, потому что сумма 1 перемещается с индекса 1 на индекс 4.
Окно, которое сужается, пока его сумма больше k, также возвращает 4 в первом примере. В итоге в нём остаётся [-1, 3, 1, -4, 2, 3] с суммой 4, и оно так и не удаляет -1.
Если не учитывать сумму 0 на индексе -1, будут пропущены все совпадения, начинающиеся с индекса 0: для [5, 0, 0, 0] и k = 5 возвращается 0 вместо 4.
Сохранённый индекс указывает на позицию перед подмассивом, поэтому его длина равна i - start. Прибавление 1 даёт лишний элемент.

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

Какова временная сложность задачи «Самый длинный подмассив с суммой K»?

Время O(n) и дополнительная память O(n) благодаря накопительным суммам и отображению первых индексов: один поиск и не более одной вставки на элемент. Построение каждого подмассива, начиная с каждого элемента, требует времени O(n²) и памяти O(1).

Почему скользящее окно не работает, если в массиве есть отрицательные числа?

Алгоритм скользящего окна предполагает, что добавление элемента увеличивает сумму, а удаление элемента уменьшает её. При наличии отрицательных значений окно с чрезмерно большой суммой всё ещё может достичь k, когда добавится отрицательный элемент, а окну с недостаточно большой суммой может потребоваться удалить отрицательный элемент слева. Окно не может определить, какой шаг правильный.

Можно ли решить задачу «Самый длинный подмассив с суммой K» за O(1) дополнительной памяти?

Только если ни одно значение не отрицательное. Тогда сумма никогда не уменьшается при увеличении окна, и два указателя находят самое длинное окно с суммой k за время O(n) и с затратами памяти O(1). При наличии отрицательных значений нужна карта сумм или перебор за O(n²).

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

Тест #1

Тест #2

Тест #3

Аргументы

nums = [2, -1, 3, 1, -4, 2, 3]
k = 5

Ожидаемый вывод