Просто знать 15 важных паттернов, которые помогут облегчить тернистый путь в решении алгоритмических задач. Про эти паттерны мы и расскажем в этой статье.

На сегодняшний день алгоритмические задачи встречаются не только в FAANG. Многие компании и на отечественном рынке всё чаще вводят дополнительный алгоритмический этап на собеседовании – и знание алгоритмов становится отличным «плюсиком» не только при трудоустройстве, но и в решении повседневных задач. Взглянем подробнее на эти паттерны.

Прорешав более 1500 задач в LeetCode, я пришёл в такому выводу:

LeetCode - это не столько о том, сколько задач ты решил, сколько о том, сколько паттернов ты знаешь.

Знание паттернов поможет вам решать больше задач за меньшее время и быстрее определить подход к решению задачи, с которой вы раньше не сталкивались.

В этой статье мы разберём 15 видов паттернов, которые сделали мой опыт в LeetCode менее болезненным. Я подробно разберу каждый из них и оставлю ссылки на задачи в LeetCode, чтобы вы могли попрактиковаться.

1. Префиксные суммы (Prefix Sum)

Префиксная сумма включает предварительную обработку массива для создания нового массива, где каждый элемент с индексом i представляет собой сумму массива от начала до i. Это позволяет эффективно выполнять запросы сумм к подмассивам.

Когда использовать: в ситуации, когда нужно выполнить несколько запросов сумм к подмассиву или вычислить совокупные суммы.

Пример задачи:

Дан массив nums. Вычислите сумму элементов в диапазоне [i, j].

Пример:

• Вход: nums = [1, 2, 3, 4, 5, 6], i = 1, j = 3

• Выход: 9

Объяснение:

• Создаём префиксный массив: P = [1, 3, 6, 10, 15, 21]

• Сумма элементов будет равна [i, j] = P[j] - P[i-1] (при i > 0)

Применимо к задачам:

• Range Sum Query - Immutable (LeetCode #303)

• Contiguous Array (LeetCode #525)

• Subarray Sum Equals K (LeetCode #560)

Пример решения на Java: ссылка

2. Два указателя (Two pointers)

Паттерн двух указателей использует два указателя для обхода массива или списка. Часто применяется для поиска пар элементов, удовлетворяющих определённому условию.

Когда использовать: при работе с отсортированными массивами или списками, где нужно найти пары, удовлетворяющие условию (например, сумма = target).

Пример задачи:

Найти два числа в отсортированном массиве, сумма которых равна заданному значению.

Пример:

• Вход: nums = [1, 2, 3, 4, 6], target = 6

• Выход: [1, 3] (индексы)

Объяснение:

• Инициализируем указатели: left = 0, right = len(nums) – 1

• Проверяем сумму элементов по двум указателям

• Если nums[left] + nums[right] == target → нашли решение

• Если сумма меньше — двигаем left вправо

• Если сумма больше — двигаем right влево

Применимо к задачам:

• Two Sum II - Input Array is Sorted (LeetCode #167)

• 3Sum (LeetCode #15)

• Container With Most Water (LeetCode #11)

Пример решения на Java: ссылка

3. Скользящее окно (Sliding Window)

Шаблон скользящего окна используется для поиска подмассива или подстроки, удовлетворяющей определённому условию. Он оптимизирует временную сложность за счёт поддержания «окна» фиксированного или переменного размера.

Когда использовать: при работе с непрерывными подмассивами или подстроками.

Пример задачи:

Найти максимальную сумму подмассива размера k.

Пример:

• Вход: nums = [2, 1, 5, 1, 3, 2], k = 3

• Выход: 9

Объяснение:

• Считаем сумму первых k элементов

• Затем «скользим» окно: вычитаем уходящий элемент, прибавляем входящий

• Отслеживаем максимальную сумму

Применимо к задачам:

• Maximum Average Subarray I (LeetCode #643)

• Longest Substring Without Repeating Characters (LeetCode #3)

• Minimum Window Substring (LeetCode #76)

Пример решения на Java: ссылка

4. Быстрый и медленный указатели (Fast & Slow Pointers)

Этот шаблон (известен как «черепаха и заяц») используется для обнаружения циклов в связных списках и других структурах.

Когда использовать: когда нужно определить наличие цикла, найти середину списка или решить задачи на цикличность.

Пример задачи:

Определить, содержит ли связный список цикличность.

Объяснение:

• Инициализируем два указателя: slow (1 шаг за итерацию), fast (2 шага)

• Если fast и slow встречаются — цикличность есть

• Если fast дошёл до конца — цикличности нет

Применимо к задачам:

• Linked List Cycle (LeetCode #141)

• Happy Number (LeetCode #202)

• Find the Duplicate Number (LeetCode #287)

Пример решения на Java: ссылка

5. Разворот связного списка на месте (In-place Reversal of LinkedList)

Этот шаблон позволяет разворачивать часть связного списка без дополнительного пространства.

Когда использовать: когда нужно развернуть подсписок или весь список «на месте».

Пример задачи:

Развернуть подсписок с позиции m по n.

Пример:

• Вход: head = [1, 2, 3, 4, 5], m = 2, n = 4

• Выход: [1, 4, 3, 2, 5]

Объяснение:

• Находим узлы до m и после n

• Разворачиваем участок между ними, корректируя указатели

Применимо к задачам:

• Reverse Linked List (LeetCode #206)

• Reverse Linked List II (LeetCode #92)

• Swap Nodes in Pairs (LeetCode #24)

Пример решения на Java: ссылка

6. Монотонный стек (Monotonic Stack)

Монотонный стек поддерживает элементы в стеке в строго возрастающем или убывающем порядке. Часто используется для поиска следующего большего/меньшего элемента.

Когда использовать: когда нужно найти ближайший больший/меньший элемент слева или справа.

Пример задачи:

Для каждого элемента массива найти следующий больший элемент. Если такого нет — вывести -1.

Пример:

• Вход: nums = [2, 1, 2, 4, 3]

• Выход: [4, 2, 4, -1, -1]

Объяснение:

• Используем стек чтобы отслеживать элементы, для которых мы еще не нашли следующий больший элемент

• Перебираем массив и извлекаем элементы из стека для каждого элемента, пока не найдем больший элемент

• Если стек не пуст, устанавливаем результат для индекса наверху стека в текущий элемент

• Помещаем текущий элемент в стек

Применимо к задачам:

• Next Greater Element I (LeetCode #496)

• Daily Temperatures (LeetCode #739)

• Largest Rectangle in Histogram (LeetCode #84)

Пример решения на Java: ссылка

7. Топ K элементов (Top ‘K’ Elements)

Этот шаблон находит K наибольших или наименьших элементов с помощью куч (heap) или сортировки.

Когда использовать: при поиске медианы, топ-K элементов в потоке.

Пример задачи:

Найти K-й по величине элемент в неотсортированном массиве.

Пример:

• Вход: nums = [3, 2, 1, 5, 6, 4], k = 2

• Выход: 5

Объяснение:

• Используем минимальную кучу (min-heap) размера k, чтобы отслеживать k крупнейших элементов

• Перебираем массив, добавляя элементы в кучу

• Если размер кучи превышает k, удаляем из кучи наименьший элемент

• Корнем кучи будет k-й по величине элемент

Применимо к задачам:

• Kth Largest Element in an Array (LeetCode #215)

• Top K Frequent Elements (LeetCode #347)

• Find K Pairs with Smallest Sums (LeetCode #373)

Пример решения на Java: ссылка

8. Перекрывающиеся интервалы (Overlapping Intervals)

Шаблон для слияния или обработки интервалов, которые пересекаются.

Когда использовать: при работе с графиками, расписаниями, объединением диапазонов.

Пример задачи:

Слить все перекрывающиеся интервалы.

Пример:

• Вход: [[1,3], [2,6], [8,10], [15,18]]

• Выход: [[1,6], [8,10], [15,18]]

Объяснение:

• Сортируем интервалы по началу

• Создаем пустой список с именем merged для хранения объединенных интервалов

• Перебираем интервалы и проверяем, не перекрывается ли они с последним интервалом в объединенном списке

• Если они перекрываются, объединяем интервалы, обновив время окончания последнего объединенного интервала

• Если они не пересекаются, просто добавляем текущий интервал в объединенный список

Применимо к задачам:

• Merge Intervals (LeetCode #56)

• Insert Interval (LeetCode #57)

• Non-Overlapping Intervals (LeetCode #435)

Пример решения на Java: ссылка

9. Модифицированный бинарный поиск (Modified Binary Search)

Адаптация бинарного поиска для вращённых отсортированных массивов, нахождения границ и т.д.

Когда использовать: при работе с отсортированными или повёрнутыми массивами и поиске элементов.

Пример задачи:

Найти элемент в повёрнутом отсортированном массиве.

Пример:

• Вход: nums = [4,5,6,7,0,1,2], target = 0

• Выход: 4 (индекс)

Объяснение:

• Выполняем двоичный поиск с дополнительной проверкой, чтобы определить, какая половина массива отсортирована

• Затем проверяем, находится ли цель в пределах отсортированной половины

• Если да, ищем эту половину; в противном случае ищем вторую половину

Применимо к задачам:

• Search in Rotated Sorted Array (LeetCode #33)

• Find Minimum in Rotated Sorted Array (LeetCode #153)

• Search a 2D Matrix II (LeetCode #240)

Пример решения на Java: ссылка

10. Обход бинарного дерева (Binary Tree Traversal)

Обход всех узлов дерева в определённом порядке:

• PreOrder: корень → лево → право

• InOrder: лево → корень → право

• PostOrder: лево → право → корень

Когда использовать: почти во всех задачах на деревья.

Пример задачи:

Выполнить inorder-обход.

Пример:

• Вход: root = [1, null, 2, 3]

• Выход: [1, 3, 2]

Объяснение:

• При неупорядоченном обходе узлы посещаются в следующем порядке: левый, корневой, правый.

• Используем рекурсию или стек для обхода дерева в этом порядке.

Применимо к задачам:

• PreOrder → Binary Tree Paths (LeetCode #257)

• InOrder → Kth Smallest Element in a BST (LeetCode #230)

• PostOrder → Binary Tree Maximum Path Sum (LeetCode #124)

Пример решения на Java: ссылка

11. Поиск в глубину (DFS)

Погружаемся как можно глубже по одной ветке, прежде чем вернуться назад.

Когда использовать: для обхода всех путей, генерации комбинаций, рекурсивных задач на деревья/графы.

Пример задачи:

Найти все пути от корня до листьев.

Пример:

• Вход: root = [1,2,3,null,5]

• Выход: ["1->2->5", "1->3"]

Объяснение:

• Используем рекурсию или стек для прохождения каждого пути от корня к листьям.

• Записываем каждый путь по мере прохождения.

Применимо к задачам:

• Clone Graph (LeetCode #133)

• Path Sum II (LeetCode #113)

• Course Schedule II (LeetCode #210)

Пример решения на Java: ссылка

12. Поиск в ширину (BFS)

Узлы исследуются уровень за уровнем в дереве или графе.

Когда использовать: для поиска кратчайшего пути в невзвешенном графе, обхода по уровням.

Пример задачи:

Выполнить уровневый обход бинарного дерева.

Пример:

• Вход: root = [3,9,20,null,null,15,7]

• Выход: [[3], [9,20], [15,7]]

Объяснение:

• Используем очередь для отслеживания узлов на каждом уровне.

• Проходим каждый уровень и добавляем в очередь дочерние элементы текущих узлов.

Применимо к задачам:

• Binary Tree Level Order Traversal (LeetCode #102)

• Rotting Oranges (LeetCode #994)

• Word Ladder (LeetCode #127)

Пример решения на Java: ссылка

13. Обход матрицы (Matrix Traversal)

Обход элементов матрицы с помощью DFS, BFS и других техник.

Когда использовать: при работе с двумерной сеткой (grid) или матрицой, островами, заливкой и т.п.

Пример задачи:

Выполнить заливку (flood fill) — изменить цвет всех смежных клеток, начиная с заданной.

Пример:

• Вход: image = [[1,1,1],[1,1,0],[1,0,1]], sr = 1, sc = 1, newColor = 2

• Выход: [[2,2,2],[2,2,0],[2,0,1]]

Объяснение:

• Используем DFS или BFS для перемещения по матрице, начиная с заданной ячейки.

• Изменяем цвет соединенных ячеек на новый цвет.

Применимо к задачам:

• Flood Fill (LeetCode #733)

• Number of Islands (LeetCode #200)

• Surrounded Regions (LeetCode #130)

Пример решения на Java: ссылка

14. Возврат (Backtracking)

Backtracking перебирает все возможные решения, откатываясь при неудаче.

Когда использовать: для задач на перестановки, комбинации, размещения, судоку и т.д.

Пример задачи:

Сгенерировать все перестановки списка.

Пример:

• Вход: nums = [1,2,3]

• Выход: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Объяснение:

• Используем рекурсию для создания перестановок.

• Для каждого элемента включаем его в текущую перестановку и рекурсивно сгенерируем оставшиеся перестановки.

• Возвращаемся назад, когда сгенерированы все перестановки для данного пути.

Применимо к задачам:

• Permutations (LeetCode #46)

• Subsets (LeetCode #78)

• N-Queens (LeetCode #51)

Пример решения на Java: ссылка

15. Динамическое программирование (Dynamic Programming)

ДП разбивает задачу на подзадачи и решает их, избегая повторных вычислений.

Когда использовать: когда есть перекрывающиеся подзадачи и оптимальная подструктура.

Подтипы ДП:

• Числа Фибоначчи

• Рюкзак (0/1 Knapsack)

• Наибольшая общая подпоследовательность (LCS)

• Наибольшая возрастающая подпоследовательность (LIS)

• Сумма подмножества

• Умножение цепочки матриц

Пример задачи:

Найти n-е число Фибоначчи.

Пример:

• Вход: n = 5

• Выход: 5 (последовательность: 0, 1, 1, 2, 3, 5)

Объяснение:

• Используем восходящий подход для вычисления n-го числа Фибоначчи.

• Начинаем с первых двух чисел (0 и 1) и выполняем итерацию для вычисления следующих чисел, например (dp[i] = dp[i - 1] + dp[i - 2]).

Применимо к задачам:

• Climbing Stairs (LeetCode #70)

• House Robber (LeetCode #198)

• Coin Change (LeetCode #322)

• Longest Common Subsequence (LCS) (LeetCode #1143)

• Longest Increasing Subsequence (LIS) (LeetCode #322)

• Partition Equal Subset Sum (LeetCode #416)

Пример решения на Java: ссылка

Все решения в нашем GitLab: ссылка