Самый короткий маршрут с точным бюджетом

В городе Нумероград дежурный дрон летит вдоль одной прямой улицы, где подряд стоят n кварталов. У каждого квартала есть «стоимость пролёта» — целое число (может быть отрицательным: иногда дрон подзаряжается).

Дрон хочет выбрать один непрерывный отрезок кварталов (хотя бы один квартал), чтобы суммарная стоимость на этом отрезке была ровно S. Из всех таких вариантов дрону нужен маршрут с минимальным числом кварталов.

Найдите длину самого короткого подходящего отрезка. Если подходящего отрезка нет — выведите -1.

Важно: суммы могут не помещаться в 32-битный тип (как на олимпиадах), используйте 64-битные целые. В Python это уже учтено.

Формат ввода 1) В первой строке: два целых числа n и S. 2) Во второй строке: n целых чисел a1, a2, ..., an — стоимости кварталов.

Формат вывода Одно целое число: минимальная длина отрезка с суммой ровно S, или -1.

Ограничения

• 1 ≤ n ≤ 20000
• -100000 ≤ ai ≤ 100000
• 0 ≤ |S| ≤ 1000000000

Пример Ввод:

6 3
1 -1 2 3 -2 1

Вывод:

1

Ключевое наблюдение: сумма на отрезке (i+1…j) равна pref[j] - pref[i], где pref[k] — сумма первых k элементов. Значит, отрезок с суммой S существует тогда и только тогда, когда для текущего pref[j] найдётся такой pref[i], что pref[i] = pref[j] - S.

Почему работает хеш-таблица: мы хотим быстро (за O(1)) находить, был ли уже нужный префикс, и какой индекс i даёт самый короткий отрезок.

Важно про «самый короткий»: при фиксированном j длина j - i минимальна, если i максимально возможен. Поэтому для каждого значения префиксной суммы выгодно хранить не самый ранний, а самый поздний индекс.

План решения:

• Идём слева направо, считаем текущий префикс pref.
• Держим словарь latest, где latest[x] = самый поздний индекс, на котором встречался префикс x.
• На шаге j считаем need = pref - S (то есть какой префикс должен быть слева).
• Если need есть в latest, обновляем ответ: best = min(best, j - latest[need]).
• Затем записываем latest[pref] = j (перезаписываем, чтобы индекс был максимально поздним).
• Если ответ не обновлялся — выводим -1.

Сложность: O(n) по времени и O(n) по памяти.

Частая ошибка: хранить первый (самый ранний) индекс префикса — тогда вы получите самый длинный отрезок, а не самый короткий. Ещё грабли: «скользящее окно» не подходит из-за отрицательных чисел.