Подход	Коротко что это	Где часто встречается	Типичная сложность
2 указателя (two pointers)	два индекса двигаются по массиву/строке и “сходятся” или идут параллельно	слияние отсортированных, two sum в отсортированном, палиндромы, partition	часто O(n)
Словарь (map/set, хеш-таблица)	кладем в ассоц массив для быстрых проверок/счетчиков	two sum, дубликаты, частоты, пересечения, группировки	часто O(n)
Жадный алгоритм (greedy)	на каждом шаге берешь локально лучший вариант	сдача монет, интервалы, расписания, “макс выгода”	обычно O(n log n) из-за сортировки
Динамическое программирование (DP)	решаем через подзадачи + запоминаем результаты	рюкзак, пути, подстроки, “максимум/минимум при условиях”	часто O(n*m) или O(n)
Рекурсия + мемоизация	рекурсия, но чтобы не считать одно и то же, кешируем	fib, пути, комбинации, game DP	зависит от задачи
Разделяй и властвуй	разбили на части, решили, склеили	merge sort, quick sort, бинарный поиск	часто O(n log n)
Бинарный поиск	ищем по отсортированному или по “монотонному условию”	поиск в массиве, “минимальное подходящее значение”	O(log n) или O(n log X)
Скользящее окно (sliding window)	окно [l..r] двигается, поддерживаем условие	подмассивы/подстроки, суммы, “самый длинный”	часто O(n)
Стек/монотонный стек	храним кандидатов, выкидываем лишнее	ближайший больший/меньший, скобки, daily temperatures	O(n)
Очередь/монотонная очередь	как стек, но для окон: максимум/минимум в окне	max/min в sliding window	O(n)
Сортировка как прием	“отсортируй и станет легко”	уникальные, интервалы, two pointers после сортировки	O(n log n)
BFS (поиск в ширину)	слоями от старта	кратчайший путь в невзвешенном графе, лабиринт	O(V+E)
DFS (в глубину)	идем вглубь, потом назад	компоненты связности, топология, обходы	O(V+E)
Backtracking	перебор с откатом, часто с отсечениями	комбинации, перестановки, n-queens, sudoku	часто экспонента
Префиксные суммы	заранее считаем суммы до i	суммы на отрезке, подмассив с суммой, частые запросы	подготовка O(n), запрос O(1)
Разностный массив	обновления диапазонов без полного прохода	массовые прибавки на диапазоне	обновление O(1), финал O(n)
Union-Find (DSU)	объединять множества и проверять связность	“острова”, компоненты, MST (Краскал)	почти O(1) амортизированно
Куча (heap, priority queue)	быстро доставать min/max	топ-K, планировщики, Dijkstra	операции O(log n)

Как “правильно приступать” к задаче

Есть набор “сигналов”, по которым почти всегда угадывается подход:

1. Отсортировано, или можно отсортировать без потери смысла
   Часто это:

• two pointers
• бинарный поиск
• merge / “слить два массива”
• задачи на интервалы (greedy + sort)

2. “Нужно найти пару/сумму/повтор/частоты/пересечение”
   Почти всегда:

• словарь (map/set)

3. “Самая длинная подстрока/подмассив с условием”, “окно”, “подряд”
   Почти всегда:

• sliding window
• иногда + словарь (для подсчета в окне)

4. “Много запросов суммы на отрезке”, “сумма/кол-во от L до R”
   Почти всегда:

• префиксные суммы
• иногда разностный массив (если много обновлений диапазонов)

5. “Ближайший больший/меньший справа/слева”, “скобки”, “температуры”, “гистограмма”
   Почти всегда:

• стек или монотонный стек

6. “Найти кратчайший путь в лабиринте/по клеткам без весов”
   Почти всегда:

• BFS

7. “Все варианты”, “перебрать комбинации”, “расставить”, “выбрать подмножество”
   Почти всегда:

• backtracking (и дальше думать про отсечения)

8. “Оптимум: максимум/минимум при ограничениях”, “выбрать лучшее, но есть зависимость от прошлого”
   Очень часто:

• DP (динамика)
  Сигнал: “решение для i зависит от i-1 / i-2 / чего-то меньшего”.

9. “Есть условие монотонности по ответу: если X подходит, то все больше тоже подходят”

• binary search on answer
  Типовой пример: минимальная скорость/время/размер, чтобы уложиться.

С книги “Грокаем алгоритмы”.

Методы решения задач рассматриваются в главах 4, 8 и 9. Если вы столкнулись со сложной задачей и не знаете , как эффективно ее решить, воспользуйтесь стратегией «разделяй и властвуй» (глава 4) или методом динамического программирования (глава 9). А если вы поняли , что эффективного решения не существует, попробуйте получить приближенный ответ с использованием жадного алгоритма (глава 8).