Minimum Size Subarray Sum

Средняя№209переменный размер

Дан массив положительных чисел и число target. Найди длину самого короткого отрезка подряд идущих чисел с суммой не меньше target или 0, если такого нет. Наш пример: [3, 1, 4, 2, 6, 5, 1] и target = 11 — ответ 2: 6 + 5 = 11.

209 Minimum Size Subarray SumРазбор · 1×

Пример: [3, 1, 4, 2, 6, 5, 1], target = 11. Хорошее окно, с суммой не меньше 11, закрашено как найденное.

03112432465561sum0target11best–
ещё не дошлиокновходящее числоуходящее числовышло из окнахорошее окно

Окно пустое: sum = 0

01/46
сначала · назад · пуск · шаг
Скорость
1function minSubArrayLen(target, nums):
2 sum = 0
3 left = 0
4 best = infinity
5 for right from 0 to len(nums) - 1:
6 sum = sum + nums[right]
7 while sum >= target:
8 best = min(best, right - left + 1)
9 sum = sum - nums[left]
10 left = left + 1
11 if best == infinity:
12 return 0
13 return best
состояние
sum
0
left
–
right
–
best
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

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

  1. Все числа положительные, поэтому у длинного окна сумма больше. Если окно хорошее, то и все окна длиннее с тем же правым краем хорошие, но короче они не станут: проверять стоит только то, что получится при сужении.
  2. Длина записывается во время сужения, на каждом хорошем окне, а сужаем, пока сумма не станет меньше target. Так для каждого right измеряется самое короткое хорошее окно, которое кончается на нём.
  3. Убирать число на left безопасно: окно от left до right было хорошим и уже измерено, а окно с тем же left и следующим right кончалось бы правее, то есть было бы только длиннее.

Сложность

Время O(n): right проходит каждое число один раз, left — не больше одного раза, поэтому внутренний цикл за всё время выполняется не больше n раз. Память O(1).

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.