Нахождение непрерывного подпоследовательности с заданной суммой

Условие

Дан массив целых чисел. Требуется определить непустой подмассив (непрерывный отрезок) сумма элементов которого равна заданному значению target, либо вывести, что такого отрезка нет. Пример: [9, -6, 5, 1, 4, -2], 10 → (2, 4)

Ответ

Используйте префиксную сумму и таблицу уже встреченных сумм. Если текущая сумма равна S, нужен предыдущий префикс S − target. Метод работает и при отрицательных числах.

Индексы результата — с нуля, обе границы включены:

def find_subarray(arr, target):
    first = {0: -1}
    prefix = 0
    for right, value in enumerate(arr):
        prefix += value
        previous = first.get(prefix - target)
        if previous is not None:
            return previous + 1, right
        first.setdefault(prefix, right)
    return None

Пример возвращает (2, 4). Поиск выполняется до добавления текущего префикса, поэтому не возвращает пустой отрезок при target = 0. В среднем время O(n), память O(n). Обычное скользящее окно для произвольных отрицательных чисел не подходит.