Содержание
Что такое техника двух указателей?
Техника двух указателей — это использование двух указателей в массиве для эффективного решения задач.
Шаблоны
3 распространенных метода двух указателей:
- Скользящее окно
- Указатели с двух концов
- Быстрые и медленные указатели
Скользящее окно
Раздвижное окно можно использовать для поиска чего-либо в подмассиве.
def get_counter():
pass
def condition():
pass
def do_something_before():
pass
def do_something_after():
pass
def sliding_window(arr):
counter = get_counter()
# outer loop to move end index
while end < len(arr):
end += 1
# start index only increase when condition
while condition():
do_something_before()
start += 1
do_something_after()
Указатели с двух концов
Указатели с двух концов можно использовать, когда задача сводится к поиску двух элементов в массиве, удовлетворяющих условию.
def condition_left():
pass
def condition_right():
pass
def do_something():
pass
def pointers_from_two_ends(arr):
left, right = 0, len(arr)-1
while left < right:
if condition_left():
left += 1
if condition_right():
right -= 1
do_something()
Быстрые и медленные указатели
Быстрые и медленные указатели могут быть использованы для:
- обнаружения циклов
- удаление дубликатов
- найти средний узел
def condition_slow():
pass
def do_something():
pass
def fast_slow_pointers(arr):
slow = 0
for fast in range(len(arr)):
# only move slow pointer when condition
if condition_slow():
slow += 1
do_something()