Скользящее окно переменной длины: минимальный подотрезок с суммой не меньше S
Задача: дан массив положительных чисел и число S, найти минимальную длину подотрезка с суммой >= S (если такого нет — 0). Понимаю окно фиксированной длины, а вот переменное окно никак не уложу в голове. Как двигать оба указателя?
2 ответа
Это классическое окно переменной длины на положительных числах. Двигаем правый указатель, расширяя окно и накапливая сумму. Как только сумма стала >= S, пытаемся сжать слева, пока условие держится, обновляя минимум. Каждый из указателей проходит массив максимум один раз → O(n).
int minLen(const vector<int>& a, long long S) {
int n = a.size(), best = n + 1;
long long sum = 0;
int l = 0;
for (int r = 0; r < n; r++) {
sum += a[r];
while (sum >= S) { // условие выполнено — сжимаем
best = min(best, r - l + 1);
sum -= a[l];
l++;
}
}
return best == n + 1 ? 0 : best;
}
Сложность O(n) время, O(1) память.
Почему это корректно и почему O(n): для каждого r мы находим самый правый l, при котором [l..r] ещё годится (сумма >= S). Левый указатель монотонно растёт. Внутренний while суммарно делает не больше n шагов за весь прогон — амортизированно O(1) на итерацию. Опять же: работает только для положительных элементов (монотонность суммы по окну). Для произвольных знаков нужна другая техника (префиксы + дек/Фенвик).
Частая ошибка реализации — обновлять best после того, как окно перестало удовлетворять условию. Обновляй ровно в тот момент, когда sum >= S, до вычитания a[l]. И храни best как заведомо «недостижимое» (n + 1), чтобы потом отличить «не найдено» от «найдено длиной n». Если в задаче нужны не положительные числа, а просто все элементы, и спрашивают «есть ли подотрезок суммой ровно S» — это уже другая задача (хеш по префиксным суммам), не путай с окном.