#Два указателя (Two Pointers)
Два указателя — паттерн, при котором два указателя движутся по массиву навстречу или в одном направлении с разной скоростью.
- Используется для отсортированных массивов
- Пример: поиск пары с заданной суммой
- Сложность: O(n) вместо O(n²)
def two_sum_sorted(arr, target):
left, right = 0, len(arr) - 1
while left < right:
current_sum = arr[left] + arr[right]
if current_sum == target:
return [left, right]
elif current_sum < target:
left += 1
else:
right -= 1
return []
#2. Разная скорость (Fast/Slow)
- Используется для обнаружения циклов в связных списках (алгоритм Флойда)
- Fast указатель движется в 2 раза быстрее slow
- Если они встречаются — есть цикл
#Скользящее окно (Sliding Window)
Скользящее окно — техника, при которой окно фиксированного или переменного размера скользит по массиву/строке.
- Размер окна постоянный
- Обновление результата инкрементально
- Пример: подмассив максимальной суммы длины k
def max_subarray_sum(arr, k):
window_sum = sum(arr[:k])
max_sum = window_sum
for i in range(k, len(arr)):
window_sum = window_sum - arr[i-k] + arr[i]
max_sum = max(max_sum, window_sum)
return max_sum
- Размер окна изменяется в зависимости от условия
- Пример: подстрока без повторяющихся символов
#Union-Find (Disjoint Set Union)
Union-Find — структура данных для объединения множеств и проверки принадлежности одному множеству.
- Find(x): находит корень элемента x
- Union(x, y): объединяет множества, содержащие x и y
- Path compression: сокращает путь до корня при каждом find
- Union by rank/size: при объединении корень с меньшим рангом становится дочерним
- Find и Union: O(α(n)) ≈ O(1), где α(n) — обратная функция Аккермана
- Практически константная сложность
- Алгоритм Краскала для минимального остовного дерева
- Поиск связных компонентов
- Обнаружение циклов в неориентированных графах
- Динамическая связность
#Практические рекомендации
-
- Два указателя: когда задача требует работы с парами элементов в массиве
- Скользящее окно: когда нужно найти подмассив/подстроку с определённым свойством
- Union-Find: когда требуется работа с множествами и их объединением
-
- Всегда начинайте с наивного решения O(n²), затем ищите возможности оптимизации
- Для двух указателей убедитесь, что данные отсортированы или можно отсортировать
- Для скользящего окна определите, как обновлять результат при перемещении окна
-
- Два указателя: 3Sum, Container With Most Water, Remove Duplicates
- Скользящее окно: Longest Substring Without Repeating Characters, Minimum Window Substring
- Union-Find: Number of Islands, Graph Valid Tree, Accounts Merge