Условие

Дан массив целых чисел, нужно найти непустой подотрезок (непрерывную подпоследовательность)

с заданной суммой target, либо сказать, что это невозможно.

find_target ([9, -6, 5, 1, 4, -2], 10) -> (2, 4)

def find_target(arr: list[int], target: int) -> tuple[int, int]: pass

Ответ

Используйте префиксные суммы: подотрезок существует, если уже встречалась сумма prefix − target. Это работает и с отрицательными числами, в отличие от обычного скользящего окна.

def find_target(arr: list[int], target: int) -> tuple[int, int]:
    positions = {0: -1}
    prefix = 0
    for right, value in enumerate(arr):
        prefix += value
        left_prefix = prefix - target
        if left_prefix in positions:
            return positions[left_prefix] + 1, right
        positions.setdefault(prefix, right)
    return -1, -1

Границы включительные, а (-1, -1) здесь выбран как признак отсутствия решения. Проверка выполняется до добавления текущей суммы, поэтому найденный отрезок непустой даже при target=0. Для примера получаем (2, 4). Ожидаемое время O(n), память O(n).