Подотрезок с суммой ровно S

1. Идея

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

Из-за этого можно применить метод двух указателей, или скользящее окно:

• правая граница r двигается слева направо;
• текущая сумма окна поддерживается в переменной;
• если сумма стала слишком большой, двигаем левую границу l, пока сумма не перестанет превышать S;
• если в какой-то момент сумма стала ровно S, ответ найден.

Такой подход позволяет найти подотрезок за линейное время.

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

Наблюдение 1

Если бы в массиве были отрицательные числа, метод двух указателей уже не работал бы так просто: при добавлении нового элемента сумма могла бы как увеличиться, так и уменьшиться.

Но в этой задаче все a_i > 0, поэтому:

• добавили a[r] — сумма увеличилась;
• убрали a[l] — сумма уменьшилась.

Это делает поведение окна предсказуемым.

Наблюдение 2

Для каждого фиксированного r нет смысла оставлять окно с суммой больше S. Раз сумма уже слишком велика, нужно уменьшать её, двигая l вправо.

Наблюдение 3

Каждый указатель движется только вперёд:

• r проходит массив один раз;
• l тоже не может сдвинуться назад.

Значит, общее число сдвигов не больше 2n, то есть решение работает за O(n).

3. Алгоритм

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

• l — левую границу текущего окна;
• sum — сумму элементов на отрезке от l до r.

Шаги:

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

Индексация в массиве внутри программы удобна с нуля, а в ответе по условию нужны номера блюд с единицы, поэтому выводим l + 1 и r + 1.

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

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

Рассмотрим текущее окно от l до r.

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

После выполнения цикла while выполняется важное свойство:

• сумма текущего окна не больше S;
• левая граница l минимально возможная среди тех, при которых окно заканчивается в r и имеет сумму не больше S.

Если в этот момент sum == S, то найден подотрезок с нужной суммой.

Если же для некоторого r подходящий подотрезок существует, алгоритм его не пропустит:

• правая граница обязательно дойдёт до этого r;
• затем левая граница будет сдвигаться вправо, пока сумма не станет не больше S;
• поскольку все числа положительные, сумма меняется строго в нужную сторону, и если существует окно с суммой ровно S, алгоритм попадёт в него.

Таким образом, если решение существует, оно будет найдено. Если алгоритм не нашёл ответ, значит такого подотрезка нет.

5. Сложность

• Время: O(n)
• Память: O(n) на хранение массива

Почему время линейное:

• указатель r делает n шагов;
• указатель l за всю программу тоже сделает не более 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];
    }

    int l = 0;
    long long sum = 0;

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

        while (sum > S && l <= r) {
            sum -= a[l];
            l++;
        }

        if (sum == S) {
            cout << l + 1 << " " << r + 1 << "\n";
            return 0;
        }
    }

    cout << -1 << "\n";
    return 0;
}

7. Код на Python 3

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

l = 0
s = 0

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

    while s > S and l <= r:
        s -= a[l]
        l += 1

    if s == S:
        print(l + 1, r + 1)
        break
else:
    print(-1)