1. Идея

Нужно найти самый короткий непрерывный подотрезок массива, сумма которого не меньше S.

Так как все a_i положительные, здесь отлично работает метод двух указателей, или скользящего окна.

Будем поддерживать текущий отрезок [l, r] и его сумму. Указатель r двигаем вправо, расширяя окно и увеличивая сумму. Как только сумма стала не меньше S, пробуем сдвигать левую границу l вправо, чтобы сделать отрезок как можно короче, но при этом не потерять условие.

На каждом таком шаге можно обновлять ответ.

2. Наблюдения

Наблюдение 1

Если бы числа могли быть отрицательными, метод двух указателей уже не был бы таким простым. Но здесь все a_i > 0.

Это очень важно: если мы двигаем правую границу вправо, сумма только растёт, а если двигаем левую границу вправо, сумма только уменьшается.

Наблюдение 2

Для фиксированной правой границы r выгодно как можно сильнее сдвинуть левую границу l вправо, пока сумма остаётся не меньше S. Тогда получим кратчайший подходящий отрезок, оканчивающийся в r.

Наблюдение 3

Каждый указатель движется только вперёд. Значит, суммарно l и r сделают не более n шагов каждый, поэтому решение будет линейным.

3. Алгоритм

Будем хранить:

• l — левую границу окна,
• current_sum — сумму элементов на текущем отрезке,
• ans — минимальную найденную длину.

Шаги:

1. Считать n, S и массив a.
2. Инициализировать:
   • l = 0,
   • current_sum = 0,
   • ans = n + 1 как признак, что ответ пока не найден.
3. Для каждого r от 0 до n - 1:
   • добавить a[r] в current_sum;
   • пока current_sum >= S:
     • обновить ответ длиной r - l + 1;
     • вычесть a[l] из суммы;
     • увеличить l на 1.
4. Если ans так и остался равен n + 1, вывести -1.
5. Иначе вывести ans.

4. Почему это работает

Докажем, что алгоритм действительно находит минимальную длину подходящего подотрезка.

Шаг 1. Что хранит окно

В любой момент рассматривается некоторый текущий отрезок [l, r], а current_sum равна сумме его элементов.

Когда мы двигаем r, мы добавляем новый элемент справа. Когда двигаем l, убираем элемент слева. Значит, сумма поддерживается корректно.

Шаг 2. Почему можно сдвигать левую границу

Как только current_sum >= S, текущий отрезок уже подходит по условию. Но он может быть не минимальным.

Так как все элементы положительные, удаление левого элемента уменьшает сумму. Поэтому, пока после удаления условие ещё выполняется, выгодно продолжать сдвигать l вправо: длина уменьшается, а отрезок всё ещё подходит.

Значит, цикл while current_sum >= S находит самый короткий подходящий отрезок для данного r.

Шаг 3. Почему не пропустим лучший ответ

Рассмотрим любой подходящий подотрезок [L, R] с суммой не меньше S.

Когда внешний цикл дойдёт до r = R, правый конец этого подотрезка уже будет рассмотрен. Внутренний цикл начнёт сдвигать левую границу вправо настолько далеко, насколько возможно. Следовательно, среди проверенных длин обязательно будет длина не больше, чем у [L, R].

Значит, алгоритм рассмотрит кандидата не хуже любого оптимального подотрезка. Поэтому минимальная длина будет найдена.

5. Сложность

• Время: O(n), потому что каждый указатель движется только вправо и не более n раз.
• Память: O(n) на хранение массива.

6. Код на C++17

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n;
    long long S;
    cin >> n >> S;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long sum = 0;
    int l = 0;
    int ans = n + 1;

    for (int r = 0; r < n; r++) {
        sum += a[r];

        while (sum >= S) {
            int len = r - l + 1;
            if (len < ans) ans = len;
            sum -= a[l];
            l++;
        }
    }

    if (ans == n + 1) {
        cout << -1 << '\n';
    } else {
        cout << ans << '\n';
    }

    return 0;
}

7. Код на Python 3

n, S = map(int, input().split())
a = list(map(int, input().split()))

l = 0
current_sum = 0
ans = n + 1

for r in range(n):
    current_sum += a[r]

    while current_sum >= S:
        length = r - l + 1
        if length < ans:
            ans = length
        current_sum -= a[l]
        l += 1

if ans == n + 1:
    print(-1)
else:
    print(ans)