0. Как вообще думать на алгоритмах

Прежде чем смотреть паттерны, держи главный порядок вопросов:

Всегда сначала спрашивай себя

Можно ли решить в лоб?
Можно ли ускорить через:
HashMap / HashSet
Two Pointers
Sliding Window
Prefix Sum
Данные отсортированы?
Нужен максимум / минимум на отрезке?
Нужно искать путь / связи / компоненты?
Есть повторяющаяся структура, которую стоит кэшировать?

1. HashMap / HashSet

Один из самых частых паттернов.

Когда использовать

нужно быстро проверять “встречалось ли”
считать частоты
группировать
хранить соответствие
искать пары

1.1. Counting / частоты

Когда

анаграммы
сколько раз встретился элемент
most frequent
проверить одинаковый состав

Шаблон мышления

Вместо повторного перебора массива я буду хранить частоту каждого элемента.

Шаблон кода

var count = new Dictionary<char, int>();

foreach (var ch in s)
{
    count[ch] = count.GetValueOrDefault(ch, 0) + 1;
}

Пример

Valid Anagram

Идея:

считаешь частоты букв в s
уменьшаешь по t
в конце всё должно стать 0

1.2. Membership / “быстро проверить наличие”

Когда

“есть ли такой элемент”
пересечение множеств
unique elements
contains duplicate

Шаблон мышления

Вместо поиска за O(n) буду проверять наличие через HashSet за O(1).

Шаблон кода

var seen = new HashSet<int>();

foreach (var x in nums)
{
    if (seen.Contains(x))
        return true;

    seen.Add(x);
}

Пример

Contains Duplicate

1.3. Mapping / отображение

Когда

соответствие символов
словарь переходов
key → value
изоморфные строки

Шаблон мышления

Хочу хранить для каждого объекта его пару / образ / следующее состояние.

Шаблон кода

var map = new Dictionary<char, char>();

for (int i = 0; i < s.Length; i++)
{
    if (map.ContainsKey(s[i]))
    {
        if (map[s[i]] != t[i])
            return false;
    }
    else
    {
        map[s[i]] = t[i];
    }
}

Пример

Isomorphic Strings

1.4. Grouping / группировка по ключу

Когда

group anagrams
сгруппировать объекты по общему признаку

Шаблон мышления

Для каждого элемента построю ключ, одинаковый для объектов одной группы.

Шаблон кода

var groups = new Dictionary<string, List<string>>();

foreach (var str in strs)
{
    string key = BuildKey(str);

    if (!groups.ContainsKey(key))
        groups[key] = new List<string>();

    groups[key].Add(str);
}

Пример

Group Anagrams

ключ: отсортированная строка
или частоты 26 букв

2. Two Pointers

Очень важный паттерн.

Когда использовать

массив отсортирован
нужно сравнивать элементы с разных сторон
нужно сжимать / переставлять in-place
искать пару
merge

2.1. Left/Right с краёв

Когда

сумма двух чисел в отсортированном массиве
palindrome
container with most water

Шаблон мышления

У меня есть левый и правый указатели. По сравнению значений решаю, кого двигать.

Шаблон кода

int left = 0, right = nums.Length - 1;

while (left < right)
{
    int sum = nums[left] + nums[right];

    if (sum == target) return true;
    if (sum < target) left++;
    else right--;
}

Пример

Two Sum II

2.2. Slow/Fast

Когда

remove duplicates
удалить элемент in-place
compress array
linked list cycle

Шаблон мышления

fast бежит по всем элементам, slow показывает, куда писать полезные.

Шаблон кода

int slow = 0;

for (int fast = 0; fast < nums.Length; fast++)
{
    if (NeedKeep(nums[fast]))
    {
        nums[slow] = nums[fast];
        slow++;
    }
}

Пример

Remove Duplicates from Sorted Array

если nums[fast] != nums[slow], двигаем slow и пишем новый уникальный

2.3. Merge двух отсортированных массивов

Когда

merge sorted arrays
minimum difference
intersection sorted arrays

Шаблон мышления

Указатели идут по двум массивам; двигаю тот, где элемент меньше.

Шаблон кода

int i = 0, j = 0;

while (i < a.Length && j < b.Length)
{
    if (a[i] == b[j])
    {
        // обработать
        i++;
        j++;
    }
    else if (a[i] < b[j])
        i++;
    else
        j++;
}

Пример

Minimum Difference Between Two Arrays

2.4. Reverse / Rotate через развороты

Когда

rotate array
reverse words
reverse subarray

Шаблон мышления

Чтобы сделать циклический сдвиг, удобно разворачивать куски.

Шаблон кода

void Reverse(int[] nums, int l, int r)
{
    while (l < r)
    {
        (nums[l], nums[r]) = (nums[r], nums[l]);
        l++;
        r--;
    }
}

Пример

Rotate Array

reverse all
reverse first k
reverse rest

3. Sliding Window

Ещё один суперчастый паттерн.

Когда использовать

подстрока / подмассив
окно фиксированного размера
окно переменного размера
максимум / минимум / longest / shortest

3.1. Fixed Size Window

Когда

максимальная средняя температура
сумма окна длины k
количество окон с условием

Шаблон мышления

Сначала считаю первое окно, потом при сдвиге убираю левый и добавляю правый.

Шаблон кода

int windowSum = 0;

for (int i = 0; i < k; i++)
    windowSum += nums[i];

int best = windowSum;

for (int r = k; r < nums.Length; r++)
{
    windowSum += nums[r];
    windowSum -= nums[r - k];
    best = Math.Max(best, windowSum);
}

Пример

Maximum Average Subarray I

3.2. Variable Size Window

Когда

longest substring without repeating chars
minimum size subarray sum
at most k distinct
exactly k via atMost

Шаблон мышления

Расширяю окно вправо, а если условие ломается — сжимаю слева.

Шаблон кода

int left = 0;
for (int right = 0; right < s.Length; right++)
{
    Add(s[right]);

    while (!IsValid())
    {
        Remove(s[left]);
        left++;
    }

    UpdateAnswer(left, right);
}

Пример

Longest Substring Without Repeating Characters

добавляешь символ
пока дубликат — двигаешь left

3.3. Distinct count in window

Когда

все символы уникальны
количество разных символов
анаграмма в окне

Шаблон мышления

В окне храню частоты; по размеру словаря понимаю, сколько разных элементов.

Шаблон кода

var freq = new Dictionary<char, int>();

void Add(char c)
{
    freq[c] = freq.GetValueOrDefault(c, 0) + 1;
}

void Remove(char c)
{
    freq[c]--;
    if (freq[c] == 0)
        freq.Remove(c);
}

Пример

Окно длины k, проверка freq.Count == k
=> все символы в окне разные

4. Prefix Sum / Prefix Count

Когда использовать

сумма отрезка
количество чего-то на префиксе
range query
subarray sum equals k

4.1. Prefix Sum array

Когда

много запросов суммы на диапазоне
быстро считать сумму [l..r]

Шаблон мышления

Сохраняю суммы префиксов, чтобы сумму отрезка получать вычитанием.

Шаблон кода

int[] pref = new int[n + 1];

for (int i = 0; i < n; i++)
    pref[i + 1] = pref[i] + nums[i];

// sum(l..r)
int sum = pref[r + 1] - pref[l];

Пример

Range Sum Query

4.2. Prefix sum + HashMap

Когда

subarray sum equals k
число подмассивов с нужной суммой

Шаблон мышления

Если prefix[j] - prefix[i] = k, то нужен ранее встреченный prefix = current - k.

Шаблон кода

var map = new Dictionary<int, int>();
map[0] = 1;

int prefix = 0;
int count = 0;

foreach (var x in nums)
{
    prefix += x;

    if (map.ContainsKey(prefix - k))
        count += map[prefix - k];

    map[prefix] = map.GetValueOrDefault(prefix, 0) + 1;
}

Пример

Subarray Sum Equals K

5. Intervals

Когда использовать

merge intervals
insert interval
meeting rooms
overlap

5.1. Sort + Merge

Когда

объединить пересекающиеся интервалы

Шаблон мышления

Сначала сортирую по началу, потом либо расширяю текущий интервал, либо начинаю новый.

Шаблон кода

intervals.Sort((a, b) => a[0].CompareTo(b[0]));

var result = new List<int[]>();
int[] cur = intervals[0];

foreach (var interval in intervals.Skip(1))
{
    if (interval[0] <= cur[1])
        cur[1] = Math.Max(cur[1], interval[1]);
    else
    {
        result.Add(cur);
        cur = interval;
    }
}
result.Add(cur);

Пример

Merge Intervals

6. Binary Search

Когда использовать

массив отсортирован
ищем минимальный / максимальный ответ
monotonic condition

6.1. Обычный бинарный поиск

Когда

найти элемент
lower bound / upper bound

Шаблон мышления

Если условие выполнено в середине, нужный ответ либо тут, либо слева/справа.

Шаблон кода

int left = 0, right = nums.Length - 1;

while (left <= right)
{
    int mid = left + (right - left) / 2;

    if (nums[mid] == target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
}

Пример

Binary Search

6.2. Binary search on answer

Когда

минимально возможное x, при котором условие true
maximum feasible / minimum feasible

Шаблон мышления

Ответ не ищу напрямую; ищу по свойству “для этого x уже можно / ещё нельзя”.

Шаблон кода

int left = low, right = high;

while (left < right)
{
    int mid = left + (right - left) / 2;

    if (Can(mid))
        right = mid;
    else
        left = mid + 1;
}
return left;

Пример

Capacity To Ship Packages Within D Days

7. Stack

Когда использовать

скобки
next greater element
evaluate expression
undo / path
monotonic stack

7.1. Обычный stack

Когда

valid parentheses
reverse / DFS iterative
calculator

Шаблон мышления

Мне нужен LIFO: последний вошёл — первый вышел.

Шаблон кода

var stack = new Stack<char>();

foreach (var ch in s)
{
    if (IsOpen(ch))
        stack.Push(ch);
    else
    {
        if (stack.Count == 0) return false;
        if (!Match(stack.Pop(), ch)) return false;
    }
}
return stack.Count == 0;

Пример

Valid Parentheses

7.2. Monotonic Stack

Когда

next greater element
daily temperatures
largest rectangle
stock span

Шаблон мышления

В стеке храню элементы в монотонном порядке; когда новый ломает порядок — значит нашёл ответ для тех, кто сверху.

Шаблон кода

var stack = new Stack<int>(); // индексы

for (int i = 0; i < nums.Length; i++)
{
    while (stack.Count > 0 && nums[i] > nums[stack.Peek()])
    {
        int idx = stack.Pop();
        ans[idx] = i - idx;
    }
    stack.Push(i);
}

Пример

Daily Temperatures

8. Queue / Deque

Когда использовать

BFS
окно максимумов
sliding window min/max

8.1. Queue для BFS

Когда

кратчайший путь без весов
level traversal
grid BFS

Шаблон мышления

Иду по уровням: сначала все узлы на расстоянии d, потом d+1.

Шаблон кода

var q = new Queue<int>();
q.Enqueue(start);
visited.Add(start);

while (q.Count > 0)
{
    int cur = q.Dequeue();

    foreach (var nei in graph[cur])
    {
        if (visited.Add(nei))
            q.Enqueue(nei);
    }
}

Пример

Shortest Path in Unweighted Graph

8.2. Monotonic deque

Когда

sliding window maximum

Шаблон мышления

В deque хранятся кандидаты на максимум, и они упорядочены по убыванию.

Шаблон кода

var dq = new LinkedList<int>(); // индексы

for (int i = 0; i < nums.Length; i++)
{
    while (dq.Count > 0 && dq.First.Value <= i - k)
        dq.RemoveFirst();

    while (dq.Count > 0 && nums[dq.Last.Value] <= nums[i])
        dq.RemoveLast();

    dq.AddLast(i);

    if (i >= k - 1)
        ans.Add(nums[dq.First.Value]);
}

Пример

Sliding Window Maximum

9. Linked List

Когда использовать

reverse list
detect cycle
merge lists
middle node

9.1. Fast/slow in linked list

Когда

middle of linked list
cycle detection

Шаблон мышления

Один идёт по 1, второй по 2. Если есть цикл — встретятся. Если нет — fast дойдёт до конца.

Шаблон кода

var slow = head;
var fast = head;

while (fast != null && fast.next != null)
{
    slow = slow.next;
    fast = fast.next.next;
}

Пример

Middle of the Linked List

9.2. Reverse linked list

Когда

reverse list
reverse sublist
palindrome list

Шаблон мышления

На каждом шаге разворачиваю ссылку назад.

Шаблон кода

ListNode prev = null, cur = head;

while (cur != null)
{
    var next = cur.next;
    cur.next = prev;
    prev = cur;
    cur = next;
}
return prev;

Пример

Reverse Linked List

10. Trees

Когда использовать

binary tree
DFS / BFS
traversal
depth, path sum, validate BST

10.1. DFS recursion

Когда

depth
path sum
symmetry
subtree

Шаблон мышления

Ответ для узла строится из ответов детей.

Шаблон кода

int Dfs(TreeNode node)
{
    if (node == null) return 0;

    int left = Dfs(node.left);
    int right = Dfs(node.right);

    return 1 + Math.Max(left, right);
}

Пример

Maximum Depth of Binary Tree

10.2. BFS by levels

Когда

level order traversal
shortest path in tree
minimum depth

Шаблон кода

var q = new Queue<TreeNode>();
q.Enqueue(root);

while (q.Count > 0)
{
    int size = q.Count;

    for (int i = 0; i < size; i++)
    {
        var node = q.Dequeue();

        if (node.left != null) q.Enqueue(node.left);
        if (node.right != null) q.Enqueue(node.right);
    }
}

Пример

Binary Tree Level Order Traversal

11. Graphs

Когда использовать

связи
компоненты связности
путь
топологический порядок
цикл

11.1. DFS / BFS на графе

Когда

number of islands
connected components
graph valid tree

Шаблон мышления

Стартую из непосещённой вершины и обхожу всю компоненту.

Шаблон кода

void Dfs(int v)
{
    visited.Add(v);

    foreach (var nei in graph[v])
    {
        if (!visited.Contains(nei))
            Dfs(nei);
    }
}

Пример

Number of Connected Components

11.2. Grid DFS/BFS

Когда

islands
flood fill
shortest path in matrix

Шаблон кода

int[][] dirs = new int[][]
{
    new[] {1, 0},
    new[] {-1, 0},
    new[] {0, 1},
    new[] {0, -1}
};

Пример

Number of Islands

11.3. Topological sort

Когда

зависимости
course schedule
DAG order

Шаблон мышления

Если у вершины нет входящих рёбер, её можно брать первой.

Шаблон кода

var indeg = new int[n];
var q = new Queue<int>();

for (int i = 0; i < n; i++)
    if (indeg[i] == 0)
        q.Enqueue(i);

while (q.Count > 0)
{
    int cur = q.Dequeue();

    foreach (var nei in graph[cur])
    {
        indeg[nei]--;
        if (indeg[nei] == 0)
            q.Enqueue(nei);
    }
}

Пример

Course Schedule II

11.4. Union-Find / DSU

Когда

компоненты связности
cycle detection
merge groups
Kruskal MST

Шаблон мышления

Поддерживаю разбиение на множества и быстро объединяю компоненты.

Шаблон кода

int Find(int x)
{
    if (parent[x] != x)
        parent[x] = Find(parent[x]);
    return parent[x];
}

void Union(int a, int b)
{
    int pa = Find(a), pb = Find(b);
    if (pa != pb) parent[pa] = pb;
}

Пример

Number of Provinces

12. Heap / Priority Queue

Когда использовать

top k
k smallest/largest
min available
merge k sorted lists

12.1. Top K with heap

Когда

top k frequent
kth largest
task scheduler variants

Шаблон мышления

Если мне нужен top-k, можно держать heap размера k.

Примерная идея

min-heap размера k
если новый лучше — вытесняет худшего

Пример

Kth Largest Element in Array

12.2. Multi-way merge

Когда

merge k sorted lists
smallest range covering lists

Шаблон мышления

В куче держу текущий минимальный элемент из каждого списка.

Пример

Merge K Sorted Lists

13. Greedy

Когда использовать

локально лучший шаг ведёт к глобально лучшему
интервалы, покрытие, прыжки, раздача

13.1. Greedy after sort

Когда

assign cookies
non-overlapping intervals
minimum arrows

Шаблон мышления

Если отсортировать и брать локально лучший вариант, можно не пожалеть об этом решении.

Пример

Non-overlapping Intervals

13.2. Greedy with running state

Когда

jump game
gas station
stock problems

Шаблон мышления

Достаточно поддерживать текущую лучшую достижимую границу / баланс / прибыль.

Пример

Jump Game

храним farthest
если дошли до индекса > farthest, ответа нет

14. Backtracking

Когда использовать

все комбинации
все перестановки
все подмножества
sudoku / n-queens

14.1. Choose / Explore / Undo

Шаблон мышления

Выбираю следующий элемент, ухожу в рекурсию, потом откатываю выбор.

Шаблон кода

void Backtrack(List<int> path, int start)
{
    result.Add(new List<int>(path));

    for (int i = start; i < nums.Length; i++)
    {
        path.Add(nums[i]);
        Backtrack(path, i + 1);
        path.RemoveAt(path.Count - 1);
    }
}

Пример

Subsets

14.2. Permutations

Когда

порядок важен

Шаблон мышления

На каждом шаге выбираю любой ещё не использованный элемент.

Пример

Permutations

15. Dynamic Programming

Не надо начинать с неё, но базу знать нужно.

Когда использовать

есть перекрывающиеся подзадачи
решение для позиции зависит от предыдущих
нужно оптимальное значение

15.1. Linear DP

Когда

climbing stairs
house robber
min cost climbing stairs

Шаблон мышления

dp[i] — ответ для первых i элементов / для позиции i.

Шаблон кода

dp[0] = ...
dp[1] = ...

for (int i = 2; i <= n; i++)
{
    dp[i] = f(dp[i - 1], dp[i - 2]);
}

Пример

Climbing Stairs

15.2. DP on strings

Когда

longest common subsequence
edit distance
palindromic subsequence

Шаблон мышления

dp[i][j] — ответ для префиксов / подстроки.

Пример

Longest Common Subsequence

15.3. 0/1 Knapsack style

Когда

выбрать / не выбрать
target sum
partition equal subset sum

Шаблон мышления

Для каждого элемента выбираю: брать или не брать.

Пример

Partition Equal Subset Sum

16. Bit Manipulation

Когда использовать

xor
parity
masks
subsets via bits

16.1. XOR tricks

Когда

single number
missing number
swap without temp иногда

Шаблон мышления

Если число встречается дважды, XOR его убирает.

Шаблон кода

int x = 0;
foreach (var num in nums)
    x ^= num;
return x;

Пример

Single Number

16.2. Bitmask for subsets

Когда

все подмножества
маленькое число состояний

Пример

Для n элементов:

маска от 0 до (1 << n) - 1

17. Math / Counting / Buckets

Когда использовать

значения ограничены
не нужен порядок, нужна частота
h-index, top-k frequent, counting sort

17.1. Counting sort idea

Когда

маленький диапазон значений
0/1/2
h-index buckets

Шаблон мышления

Вместо сортировки считаю, сколько раз встретилось каждое значение.

Пример

Sort Colors

count[0], count[1], count[2]

17.2. Buckets by frequency

Когда

Top K Frequent Elements

Шаблон мышления

Частота лежит в диапазоне 1..n, значит можно группировать по частоте.

Пример

Top K Frequent

18. Cycle Detection / Floyd

Когда использовать

linked list cycle
find duplicate number
функциональный граф

Шаблон мышления

Если из каждой вершины ровно один выход, то можно рассматривать это как список с циклом.

Шаблон кода

int slow = nums[0];
int fast = nums[0];

do
{
    slow = nums[slow];
    fast = nums[nums[fast]];
} while (slow != fast);

Пример

Find the Duplicate Number

19. String patterns

Когда использовать

parser
compress
compare patterns
scan left to right

19.1. Two strings + map

Пример

Isomorphic Strings

19.2. Build canonical form

Пример

Group Anagrams

сортированный ключ
частотный ключ

19.3. Scan and accumulate

Пример

Basic Calculator II

текущий number
последний multiplicative chunk
общий result

20. Classic interview subpatterns

Это прям мини-шпаргалка “увидел задачу → что подумать”.

Если в задаче сказано:

“отсортированный массив”

Подумай про:

two pointers
binary search

“подстрока / подмассив”

Подумай про:

sliding window
prefix sum

“частота / встречалось / unique”

Подумай про:

HashMap
HashSet
counting

“все комбинации / все варианты”

Подумай про:

backtracking

“минимум / максимум на каждом шаге”

Подумай про:

greedy
sliding window
monotonic stack/deque
DP

“граф / связи / маршруты / зависимости”

Подумай про:

DFS/BFS
topological sort
union-find

“in-place, O(1) extra memory”

Подумай про:

two pointers
reverse trick
cycle ideas
careful swaps

Очень короткие шаблоны по памяти

Two Sum

map[target - x]?

Anagram

count[++], count[--]

Remove Duplicates Sorted

slow writes, fast scans

Fixed Window

sum += in, sum -= out

Variable Window

expand right, shrink left

Prefix Sum

pref[r+1] - pref[l]

DFS

visit -> recurse neighbors

BFS

queue by levels

Merge Intervals

sort + merge overlap

Binary Search

if good(mid) -> left or right

Monotonic Stack

while new breaks order -> pop

Backtracking

choose -> recurse -> unchoose

DP

dp[i] from smaller states

Как это учить, чтобы реально запомнить

Шаг 1

Выбери 1 паттерн на день.

Например:

день 1: HashMap
день 2: Two Pointers
день 3: Sliding Window

Шаг 2

На каждый паттерн:

2 простых задачи
1 повтор вчерашней

Шаг 3

После каждой задачи отвечай:

это какой паттерн?
почему он здесь?
какой инвариант?

Твой порядок изучения

Я бы тебе советовал идти так:

Этап 1. Основа

HashMap / HashSet
Two Pointers
Sliding Window
Prefix Sum
Intervals

Этап 2. Средний уровень

Stack / Monotonic Stack
Queue / BFS
Trees DFS/BFS
Binary Search
Greedy

Этап 3. Выше среднего

Graphs
Heap
Backtracking
DP
Union-Find

Самая полезная мысль для собеса

На собесе ты не обязан “знать задачу”.

Ты должен быстро распознать:

“А, это задача на частоты”
“А, это окно фиксированного размера”
“А, тут slow/fast”
“А, тут граф зависимостей → topo sort”

Как Думать На Алгоритмах

0. Как вообще думать на алгоритмах

Всегда сначала спрашивай себя

1. HashMap / HashSet

Когда использовать

1.1. Counting / частоты

Когда

Шаблон мышления

Шаблон кода

Пример

1.2. Membership / “быстро проверить наличие”

Когда

Шаблон мышления

Шаблон кода

Пример

1.3. Mapping / отображение

Когда

Шаблон мышления

Шаблон кода

Пример

1.4. Grouping / группировка по ключу

Когда

Шаблон мышления

Шаблон кода

Пример

2. Two Pointers

Когда использовать

2.1. Left/Right с краёв

Когда

Шаблон мышления

Шаблон кода

Пример

2.2. Slow/Fast

Когда

Шаблон мышления

Шаблон кода

Пример

2.3. Merge двух отсортированных массивов

Когда

Шаблон мышления

Шаблон кода

Пример

2.4. Reverse / Rotate через развороты

Когда

Шаблон мышления

Шаблон кода

Пример

3. Sliding Window

Когда использовать

3.1. Fixed Size Window

Когда

Шаблон мышления

Шаблон кода

Пример

3.2. Variable Size Window

Когда

Шаблон мышления

Шаблон кода

Пример

3.3. Distinct count in window

Когда

Шаблон мышления

Шаблон кода

Пример

4. Prefix Sum / Prefix Count

Когда использовать

4.1. Prefix Sum array

Когда

Шаблон мышления

Шаблон кода

Пример

4.2. Prefix sum + HashMap

Когда

Шаблон мышления

Шаблон кода

Пример

5. Intervals

Когда использовать

5.1. Sort + Merge

Когда