Войти Регистрация
Алгоритмы

24. Отрезок с заданной суммой

Средняя

Даны массив целых чисел arr (могут быть отрицательные) и число target. Найдите непустой полуинтервал индексов [l, r) с суммой target и верните [l, r].

Если подходящих несколько — тот, что заканчивается раньше; из таких — самый короткий. Если нет — верните [].

В работе: Найти период, за который баланс счёта изменился ровно на заданную сумму.

Пример 1

Ввод
arr = [2, -1, 6, 3]
target = 8
Вывод
[1, 4]

−1 + 6 + 3 = 8 — индексы с 1 по 3, полуинтервал [1, 4).

Пример 2

Ввод
arr = [1, 2]
target = 10
Вывод
[]

Ограничения

  • 0 ≤ длина arr ≤ 10⁶
  • |сумма| ≤ 10¹⁵
  • Лимит — 1 с на тест.
Как вызывается ваш код Читать ввод и печатать ответ не нужно: мы вызываем функцию на каждом тесте и сравниваем то, что она вернула. print() и console.log() уходят в консоль. 
def subarray_with_sum(arr, target):
Префиксные суммыХеш-таблицацельO(n)

Источник: отчёт о Яндексе, 2021. Условие пересказано своими словами.

Давали на собеседовании? Ответов пока мало — ваш поможет.