Просто знать 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)
Применимо к задачам:
Пример решения на 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 влево
Применимо к задачам:
Пример решения на Java: ссылка
3. Скользящее окно (Sliding Window)
Шаблон скользящего окна используется для поиска подмассива или подстроки, удовлетворяющей определённому условию. Он оптимизирует временную сложность за счёт поддержания «окна» фиксированного или переменного размера.
Когда использовать: при работе с непрерывными подмассивами или подстроками.
Пример задачи:
Найти максимальную сумму подмассива размера k.
Пример:
Вход:
nums = [2, 1, 5, 1, 3, 2], k = 3Выход: 9
Объяснение:
Считаем сумму первых k элементов
Затем «скользим» окно: вычитаем уходящий элемент, прибавляем входящий
Отслеживаем максимальную сумму
Применимо к задачам:
Пример решения на Java: ссылка
4. Быстрый и медленный указатели (Fast & Slow Pointers)
Этот шаблон (известен как «черепаха и заяц») используется для обнаружения циклов в связных списках и других структурах.
Когда использовать: когда нужно определить наличие цикла, найти середину списка или решить задачи на цикличность.
Пример задачи:
Определить, содержит ли связный список цикличность.
Объяснение:
Инициализируем два указателя: slow (1 шаг за итерацию), fast (2 шага)
Если fast и slow встречаются — цикличность есть
Если fast дошёл до конца — цикличности нет
Применимо к задачам:
Пример решения на 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
Разворачиваем участок между ними, корректируя указатели
Применимо к задачам:
Пример решения на Java: ссылка
6. Монотонный стек (Monotonic Stack)
Монотонный стек поддерживает элементы в стеке в строго возрастающем или убывающем порядке. Часто используется для поиска следующего большего/меньшего элемента.
Когда использовать: когда нужно найти ближайший больший/меньший элемент слева или справа.
Пример задачи:
Для каждого элемента массива найти следующий больший элемент. Если такого нет — вывести -1.
Пример:
Вход:
nums = [2, 1, 2, 4, 3]Выход:
[4, 2, 4, -1, -1]
Объяснение:
Используем стек чтобы отслеживать элементы, для которых мы еще не нашли следующий больший элемент
Перебираем массив и извлекаем элементы из стека для каждого элемента, пока не найдем больший элемент
Если стек не пуст, устанавливаем результат для индекса наверху стека в текущий элемент
Помещаем текущий элемент в стек
Применимо к задачам:
Пример решения на 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-й по величине элемент
Применимо к задачам:
Пример решения на Java: ссылка
8. Перекрывающиеся интервалы (Overlapping Intervals)
Шаблон для слияния или обработки интервалов, которые пересекаются.
Когда использовать: при работе с графиками, расписаниями, объединением диапазонов.
Пример задачи:
Слить все перекрывающиеся интервалы.
Пример:
Вход:
[[1,3], [2,6], [8,10], [15,18]]Выход:
[[1,6], [8,10], [15,18]]
Объяснение:
Сортируем интервалы по началу
Создаем пустой список с именем merged для хранения объединенных интервалов
Перебираем интервалы и проверяем, не перекрывается ли они с последним интервалом в объединенном списке
Если они перекрываются, объединяем интервалы, обновив время окончания последнего объединенного интервала
Если они не пересекаются, просто добавляем текущий интервал в объединенный список
Применимо к задачам:
Пример решения на Java: ссылка
9. Модифицированный бинарный поиск (Modified Binary Search)
Адаптация бинарного поиска для вращённых отсортированных массивов, нахождения границ и т.д.
Когда использовать: при работе с отсортированными или повёрнутыми массивами и поиске элементов.
Пример задачи:
Найти элемент в повёрнутом отсортированном массиве.
Пример:
Вход:
nums = [4,5,6,7,0,1,2], target = 0Выход: 4 (индекс)
Объяснение:
Выполняем двоичный поиск с дополнительной проверкой, чтобы определить, какая половина массива отсортирована
Затем проверяем, находится ли цель в пределах отсортированной половины
Если да, ищем эту половину; в противном случае ищем вторую половину
Применимо к задачам:
Пример решения на Java: ссылка
10. Обход бинарного дерева (Binary Tree Traversal)
Обход всех узлов дерева в определённом порядке:
PreOrder: корень → лево → право
InOrder: лево → корень → право
PostOrder: лево → право → корень
Когда использовать: почти во всех задачах на деревья.
Пример задачи:
Выполнить inorder-обход.
Пример:
Вход:
root = [1, null, 2, 3]Выход:
[1, 3, 2]
Объяснение:
При неупорядоченном обходе узлы посещаются в следующем порядке: левый, корневой, правый.
Используем рекурсию или стек для обхода дерева в этом порядке.
Применимо к задачам:
PreOrder → Binary Tree Paths (LeetCode #257)
PostOrder → Binary Tree Maximum Path Sum (LeetCode #124)
Пример решения на Java: ссылка
11. Поиск в глубину (DFS)
Погружаемся как можно глубже по одной ветке, прежде чем вернуться назад.
Когда использовать: для обхода всех путей, генерации комбинаций, рекурсивных задач на деревья/графы.
Пример задачи:
Найти все пути от корня до листьев.
Пример:
Вход:
root = [1,2,3,null,5]Выход:
["1->2->5", "1->3"]
Объяснение:
Используем рекурсию или стек для прохождения каждого пути от корня к листьям.
Записываем каждый путь по мере прохождения.
Применимо к задачам:
Пример решения на Java: ссылка
12. Поиск в ширину (BFS)
Узлы исследуются уровень за уровнем в дереве или графе.
Когда использовать: для поиска кратчайшего пути в невзвешенном графе, обхода по уровням.
Пример задачи:
Выполнить уровневый обход бинарного дерева.
Пример:
Вход:
root = [3,9,20,null,null,15,7]Выход:
[[3], [9,20], [15,7]]
Объяснение:
Используем очередь для отслеживания узлов на каждом уровне.
Проходим каждый уровень и добавляем в очередь дочерние элементы текущих узлов.
Применимо к задачам:
Пример решения на 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 для перемещения по матрице, начиная с заданной ячейки.
Изменяем цвет соединенных ячеек на новый цвет.
Применимо к задачам:
Пример решения на 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]]
Объяснение:
Используем рекурсию для создания перестановок.
Для каждого элемента включаем его в текущую перестановку и рекурсивно сгенерируем оставшиеся перестановки.
Возвращаемся назад, когда сгенерированы все перестановки для данного пути.
Применимо к задачам:
Пример решения на 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]).
Применимо к задачам:
Пример решения на Java: ссылка
Все решения в нашем GitLab: ссылка
Комментарии (25)
mSnus
07.11.2025 16:07Вот что должно вымереть в первую очередь в эпоху AI
MaDeLa Автор
07.11.2025 16:07Думается, что алгоритмические задачки не вымрут. Этот скилл требовали на собеседованиях 10 лет назад, и, скорее всего, будут требовать ещё долго - даже в эпоху развитого AI. А значит и тренажёры по зубрёжке будут жить. Кстати, как относитесь к тому, что на собесах дают алготимические задачки решать? Считаете полезной практикой или устаревшей традицией?
Artyomcool
07.11.2025 16:07Мне это всегда казалось и продолжает казаться неплохим способом проверить замотивированность кандидата заниматься относительно длительной подготовкой к интервью. Примерно как диплом о ВО доказательство 4-6 лет "усидчивости". Поэтому с готовностью решаю алгоритмические секции, но со своей стороны при собеседованиях делаю скидку, что вообще говоря, человек не обязан знать трюк с prefix sum, будь он трижды тривиальным (когда его знаешь). Не обязан уметь вращать деревья в уме. Но если вдруг умеет и в структуры данных, и в методы работы с ними, то разговор точно пойдет и проще, и интереснее. По крайней мере, это точно интереснее, чем фреймворк А, который уже завтра будет заменён фреймворком Б.
mSnus
07.11.2025 16:07Это как в математике - есть отличники, которые вызубрили стандартные задачи, есть люди, которые на стандартных задачах научились решать любые. В первых нет никакого особого смысла. С программированием то же самое - тот ч кто выучил и пошёл дальше, намного полезнее того, кто выучил и застрял.
Panzerschrek
07.11.2025 16:07Проблема при решении задач часто заключается в том, что не очень то понятно, что какой-то из этих паттернов может быть использован. Часто требуется какое-то неявное допущение, с которым ещё не понятно истинно ли оно и как его истинность доказать, чтобы можно было этот паттерн использовать.
MaDeLa Автор
07.11.2025 16:07Да, для паттернов это частая история. Взять в том числе гоф-паттерны: когда ты впервые с ними сталкиваешься, то не осознаёшь когда их нужно применять и стремишься их использовать даже там, где не надо. Вероятнее всего по мере решения задач, придёт понимание относительно того, где какой паттерн применить. Они сами всплывут в памяти и вам останется лишь взглянуть в статью, чтобы использовать её как шпаргалку
apcs660
07.11.2025 16:07недавно ради разогрева прорешал яндекс контест по алгоритмам; литкод несколько расслабленее и не так жестко проверяет выходы за границы времени и памяти.
Иногда кажется что можно решить одним методом в лоб, но размерность 10^9 сразу требует упростить задачу а не решать перебором.
Яндекс контест показался более жестким чем литкод, особенно последняя задачка в контесте крови попила.
Вчера прислали результат - попал в топ 300 и могу соскочить с алго-интервью в Яндекс, но оно мне не надо... вообще подумываю а зачем я поперся на эти алгоритмы? Наверное потому что на рынке тишина а тренироваться нужно. На собеседовании по алгоритмам все было просто, основная проблема была не задача а непривычность решать задачу в свете софитов, я просто не мог думать. Решил на автомате, спинным мозгом, долго тупил, но в итоге прошел интервью.
Систем дизайн интервью это было что то нечто - слишком примитивное, интервьювер не в духе, я тупил "а что здесь собственно, нужно дизайнить???". Забыл какие то мелкие вещи на которые даже не смотрел. Так понимаю, ожидалось что я должен заучить типовые паттерны и отбарабанить их за полчаса (полчаса требования собирал только). Как то само по себе интервью чуть не превратилось в собачью свалку... У меня за плечами крупные реальные проекты где я находил ошибки (достаточно важные) уже после подписания дизайна. В реальности так никто не работает, времени обычно достаточно все спокойно обдумать. Рисовать схему за час полтора это базовая подготовка пехоты.
Пройду еще final интервью и наверное закруглюсь, что то работать в Яндексе расхотелось, впечатление что колесо сансары по фильтрации кандидатов крутится само по себе, как побочный бизнес и в итоге вряд ли будет толк. С точки зрения подготовки к интервью, повышения психологической устройчивости и тд, Яндекс дает хорошую возможность для кандидатов, большое спасибо за это.
15432
07.11.2025 16:07О, я так после final и закруглился, даже офер не послушал (а зря, ради интереса можно было бы)
MaDeLa Автор
07.11.2025 16:07Спасибо, что поделились - крутой, жизненный рассказ. Прямо видно, как по ходу колесо сансары проверок превращается в проверку не алгоритмов, а нервной системы ))
System Design - отдельная боль. Прекрасно вас понимаем.
Кстати, если Яндекс не выберет - не расстраивайтесь. Выбирайте MaDeLa :) У нас тоже бывают интересные задачки, но больше с доверием к опыту. Мы ценим тех, кто умеет кодить, применяя здравый смысл.
Удачи на финале - даже если просто для галочки
apcs660
07.11.2025 16:07спасибо за пожелания. Яндекс - в первую очередь тренировка, потолкался с молодежью, посмотреть что к чему потому что меня яндекс рекрутеры к себе потащили - даже не знаю, зачем я им нужен и нужен ли. В контекст залез потому что совпало по времени - решил проверить, заржавели мозги или нет - никогда специально алгоритмами не занимался чтобы пройти интервью. Заодно втянул коллегу в процесс.
Посмотрел ваш сайт - молодцы, правильным путем идете, желаю вам дальнейшего роста. У меня опыт работы в 3х стартапах - примерно представляю процесс что нужно пройти чтобы вытянуть бизнес: первый стартап в котором работал не прожил и двух лет (2000-2001 RIP); второй в котором был 2 года на ставке и 3 года на проектных контрактах, до сих пор живет, почти 30 лет уже (с 1997), но замер в размерах после того как был поглощен и стал по сути отделом; последний 3й стартап (2007-) в котором проработал 15 лет, вырос с 10 человек (когда пришел) до примерно 200 и сейчас снова сжался (подрубило СВО, аутсорсинг был в России, на индусов переключиться не получилось - да они и сами с зубами). Был у меня опыт аутстаффа, в IBM - бегал с их бейджиком на проектах. Самый веселый опыт, если честно - много полетов, хорошие проекты. С женой потом объездили пару стран на мили и бонусы в отелях. Если бы не семейные дела и моя прикованность к России сейчас, я бы снова рванул в IBM консалтинг или подобное.
Болевая точка любого стартапа это когда приходят хорошие деньги и очень важно не потерять желание работать и не зазнаться, не растерять старый "костяк" команды - пройти испытание медными трубами и поднять планку.
При управлении нужны обратные связи, положительные и отрицательные, понятная схема мотивации (конфета должна даваться сразу), вовлечение (ощущение себя частью компании), отрицательная обратная связь тоже важна (наказание). Если обратная связь разбалансирована и происходит "заболачивание" - компания впадает в фазу застоя, старения и гибнет. Будете расти - не расслабляйтесь.
У нас болевая точка началась когда компания вышла на уровень ~10 миллионов долларов официальной прибыли и пара владельцев ушли "лежать на пляжах", наняв себе CEO и прокладку из помощников - старичков при этом оставили на своих местах. Но все быстро меняется и нужно держать нос по ветру - пока СЕО писали отчеты в стиле "все хорошо прекрасная маркиза", копился технический долг, отставание и что самое главное, уходили (от скуки!) хорошие специалисты. Платили выше рынка, но люди уходили.
Примерно за 5 лет все протухло, разложилось, СЕО в итоге сбежали и когда владельцы попытались все снова собрать - не получилось. А тут еще проблемы с СВО - если вопрос как платить, решить смогли то требования клиентов о закрытии доступа и тд разорвал цепочки.
Pochemuk
07.11.2025 16:07Что-то не понял я "Шаблон № 9". Может быть потому что машинный перевод корявый?
Лучше вот такие задачки решить:
Нахождение медианного элемента: Найти медианный элемент в неотсортированном массиве за время O(n).
Поменять местами две части массива (не обязательно равной длины) за время O(n) и с использованием O(1) дополнительной памяти (на месте).
Нахождение максимальной нулевой подматрицы: Дана прямоугольная матрица n:m, заполненная, преимущественно, нулями. Некоторым её элементам присвоены единичные значения. За время O(n*m) найти наибольший (по количеству элементов - площади) прямоугольник, состоящий из одних нулей.
DanteLFC
07.11.2025 16:07Привет, спасибо за статью, как раз приходится снова вспоминать все эти истории и готовиться. В пункте 7 в примере по ссылке https://github.com/madela-team/Java/blob/master/leet-code-algorithms/src/main/java/org/madela/TopKElements.java как будто если поменять входной массив на {3, 2, 1, 6, 5, 4}; то выводом будет 6 как 2й самый большой элемент, а ведь он 1й по размеру. Или я что-то не так понял (сам шарпист, а не джавист, могу не знать нюансов класса)
DaNuN0103
07.11.2025 16:07Там используется приоритетная очередь PriorityQueue. В конструкторе по умолчанию используется natural ordering или сортировка по возрастанию, если по-нашему. Следовательно в каком бы порядке в эту очередь не делать ставки head будет равен минимальному элементу. А так как размер кучи k, то наибольший k элемент массива.
P.s если, например, создать очередь и добавить элементы 2, 3, 1PriorityQueue<Integer> prior = new PriorityQueue<>();
prior.add(2);
prior.add(3);
prior.add(1);
тоSystem.out.println(prior)- выведет [1, 3, 2]
а последовательный вызов poll() - 1, 2, 3while(!prior.isEmpty()){
System.out.print(prior.poll());
}DanteLFC
07.11.2025 16:07Спасибо! Упустил этот момент: когда быстро гуглил про этот класс при разборе примера
nomorewar
07.11.2025 16:07А в чем смысл первого шаблона (префиксный массив)? Сам префиксный массив делать же затратно, нет? Например, если там миллион элементов. Или миллиард.
artemi1x
07.11.2025 16:07Тоже не понял для чего, пример не совсем удачный, ведь можно просто просуммировать...
wataru
07.11.2025 16:07Там же написанно - когда надо много раз искать сумму. Вы тратите O(n) времени на предподсчет и потом за O(1) считаете сумму. Навиное же решение считает одну сумму за O(n). Если надо m раз считать сумму, то наивное решение будет за O(nm), а с префиксными суммами - O(n + m). Что лучше почти всегда.
Плюс, переход к префиксным суммам упрощает задачи где вы ищете массивы с каким-то свойством суммы, ибо там сумма кучи переменных заменяется на разность всего двух. Вот там примеры даже есть в статье, вроде: найти количество подмассивов дающих заданную сумму. В терминах префиксных сумм - надо найти пары чисел с заданной разницей. Эта задача гораздо проще.
King_Louis
07.11.2025 16:07Прочитайте и потренируйтесь на книге Грокаем Алгоритмы, это будет полезнее
MaDeLa Автор
07.11.2025 16:07Подтверждаем: отличная книга, хороший совет. Но одно другому не мешает. Мы в MaDeLa считаем, что чем шире арсенал подходов к решению задач, тем лучше. И классические книги, и практические паттерны вроде тех, что в статье, отлично дополняют друг друга.
AdrianoVisoccini
я бы по каждому методу по подробнее почитал бы с удовольствием
с парой-тройкой примеров в идеале...
DamonV79
Примеры не проблема, ссылки на задачи есть, а уже в самих задачах можно посмотреть лучшие варианты решения на любом языке. Порой, это буквально несколько строчек, по этому понять алгоритм не сложно. Мне это здорово помогло, когда только начинал решать задачки на Скала, я (по привычке) использовал идеоматичный функциональный подход. Увы, по скорости он сильно проигрывает (порой, но не всегда!) императивному. Возможность подсмотреть и понять, что требуется помогла выйти в лидеры.
Ну, а подробности, да, придется искать самому. Впрочем, неплохих книжек по алгоритмам хватает.
AdrianoVisoccini
книжки по алгоритмам - планирую почитать в будущем
а вот изучать решения задач и пытаться понять паттерны, это как бы возможно, но не продуктивно. Я, собственно, так и делаю, а до многих и своим умом дохожу. Но речь скорее именно о том, как понять что в данной ситуации нужнен конкретный алгоритм и как его правильно применить, как к этому прийти итд.