Мышление шаблонами
Большинство алгоритмических задач — вариации небольшого числа шаблонов. Половина успеха — узнать сигнал в условии: «отсортированный массив», «подряд идущая подпоследовательность», «кратчайший путь», «все комбинации», «лучший результат, подзадачи повторяются». Затем вы пишете код соответствующего шаблона. Этот урок — карта; у каждого шаблона в курсе есть подробная тема.
От сигнала к шаблону
| Сигнал в условии | Шаблон | Типичная сложность |
|---|---|---|
| отсортированный массив, найти пару/тройку | два указателя | O(n) |
подряд идущий подмассив/подстрока, длина k | скользящее окно | O(n) |
| «есть ли», подсчёт, повторы, поиск пары | hash map / set | O(n) |
| отсортировано или монотонно, «первый подходящий» | бинарный поиск | O(log n) |
| кратчайший путь в графе/сетке (без весов) | BFS | O(V + E) |
| компоненты, цикл, все пути | DFS | O(V + E) |
«k наибольших», медиана потока | куча | O(n log k) |
| интервалы, слияние, пересечения | сортировка + проход | O(n log n) |
| все подмножества/перестановки | backtracking | экспоненциальная |
| оптимум, подзадачи повторяются | динамическое программирование | размер таблицы |
Два указателя и скользящее окно
В отсортированном массиве идём с двух концов к центру: сумма велика — двигаем правый, мала — левый. Каждый элемент проходится не более одного раза: O(n). В окне добавляем новый элемент и убираем старый: обновление за O(1) вместо повторного суммирования. Подробнее: два указателя, скользящее окно.
