Ctrl K

Два отрезка с нужной суммой

Средняя
Дан массив положительных целых values и число goal. Отрезок — это несколько подряд идущих элементов массива (хотя бы один). Нужно выбрать два отрезка, у каждого из которых сумма ровно goal и которые не делят ни одного элемента. Среди всех таких пар найдите ту, где суммарная длина отрезков наименьшая, и верните эту длину. Если двух подходящих отрезков нет, верните -1.
Пример 1
values=[4, 1, 3, 2, 2, 5], goal=4 → 3

Отрезки с суммой 4: [4], [1, 3] и [2, 2]. Самые короткие непересекающиеся — [4] и [1, 3] или [4] и [2, 2]: длина 1 + 2 = 3.

Пример 2
values=[6, 2, 4, 6], goal=6 → 2

Есть три отрезка: [6], [2, 4] и [6]. Выгоднее всего взять обе шестёрки: 1 + 1 = 2.

Пример 3
values=[1, 2, 3, 1], goal=5 → -1

Сумму 5 даёт только [2, 3], второго отрезка нет — ответ -1.

Ограничения
  • 1 ≤ len(values) ≤ 10⁵
  • 1 ≤ values[i] ≤ 1000
  • 1 ≤ goal ≤ 10⁸
Встречал эту задачу на настоящем собесе?
Решили0
Пробовали0
Отправок0
Принято—
Темы
Похожие задачиСамый длинный общий кусок СредняяСлова, спрятанные в тексте СредняяСамая длинная цепочка с равным шагом СредняяСнять с краёв ровно столько СредняяЗаработок водителя маршрутки Средняя
загружаем Python…
Вход
values=[4, 1, 3, 2, 2, 5], goal=4
Ожидается
3

«Запустить» — первые 3 теста у тебя в браузере, «Отправить» — все 87 тестов на сервере, включая скрытые.