Дан список целых чисел и число-цель. Нужно найти такой range, чтобы сумма его элементов давала число-цель.
elements = [1, -3, 4, 5]
target = 9
result = range(2, 4) # because elements[2] + elements[3] == target
Хочется понять основную идею, чем тут можно дополнительно воспользоваться, чтобы решить за линейное время.
Самое очевидное решение, это - брать элемент и суммировать все последующие элементы до конца и проверять было ли в процессе значение равное target
, но тогда это будет довольно долго, потому что N итераций с первого элемента, N - 1 итераций со второго элемента и т.д, получается примерно квадратичная. А как можно лучше?