Префиксные суммы и два указателя
Префиксная сумма p[i] — сумма первых i чисел списка: p[0] = 0, а каждая следующая — предыдущая плюс очередное число. Сумма чисел с номерами от l до r − 1 — p[r] - p[l]: одно вычитание вместо цикла.
Это выгодно, когда вопросов про отрезки много: префиксы считают один раз, а на каждый вопрос отвечают сразу.
a = [3, 1, 4, 1, 5, 9]
p = [0]
for x in a:
p.append(p[-1] + x)
print(p)
print(p[4] - p[1])
Два указателя — два номера, которые идут по списку в одну сторону и никогда не возвращаются. Самый длинный отрезок из положительных чисел с суммой не больше s: правый край шагает вперед, а левый подтягивается, пока сумма слишком велика.
Каждый указатель проходит список один раз, поэтому работы около 2n шагов, хотя отрезков около n².
a = [2, 1, 3, 2, 4, 1]
s = 6
left = total = best = 0
for right in range(len(a)):
total += a[right]
while total > s:
total -= a[left]
left += 1
best = max(best, right - left + 1)
print(best)
Итог урока. Префиксные суммы считают один раз, а сумма любого отрезка — p[r] - p[l]. Словарь префиксов находит отрезки с нужной суммой за один проход.
Два указателя идут по списку в одну сторону: окно с ограничением на сумму или пара с нужной суммой с двух концов упорядоченного списка. Работы около n шагов вместо n².
В последнем уроке главы — практика: выберите подходящий прием для каждой задачи.
Урок пройден
Префиксные суммы и два указателя
Выполнено заданий
Очки опыта
Обракоины
Другие уроки по теме
Следующая тема
Префиксные суммы и два указателя
Префиксные суммы и два указателя в Python: сумма отрезка p[r] - p[l], словарь префиксов, окно с ограничением на сумму, пара с нужной суммой с двух концов. В 6 заданиях вы ответите на вопросы про отрезки, найдете точку равновесия, самое длинное окно, пару с суммой и отрезки с суммой k и прочитаете программу: что она выведет?