MidПрактика12 min

Паттерны с HashMap

Two Sum, Group Anagrams, Frequency Count и другие классические паттерны

AlgoHash tables

Паттерн 1: Поиск комплементарного элемента (Two Sum)

Самая известная задача на LeetCode. Классика использования HashMap.

<?php
declare(strict_types=1);

/**
 * @param int[] $nums
 * @return int[]
 */
function twoSum(array $nums, int $target): array
{
    $seen = []; // value -> index

    foreach ($nums as $i => $num) {
        $complement = $target - $num;
        if (isset($seen[$complement])) {
            return [$seen[$complement], $i];
        }
        $seen[$num] = $i;
    }

    return [];
}

// nums = [2, 7, 11, 15], target = 9
// i=0: complement=9-2=7, 7 not in []. seen=[2=>0]
// i=1: complement=9-7=2, 2 in seen! -> [0, 1]
**Сложность:** O(n) времени и O(n) памяти vs O(n²) наивного решения.

Паттерн 2: Подсчёт частоты (Frequency Counter)

<?php
declare(strict_types=1);

/**
 * @param int[] $arr
 * @return array<int, int>
 */
function frequencyCount(array $arr): array
{
    $freq = [];
    foreach ($arr as $x) {
        $freq[$x] = ($freq[$x] ?? 0) + 1;
    }
    return $freq;
}

// Or using built-in:
$freq = array_count_values([1, 2, 2, 3, 3, 3]);
// [1 => 1, 2 => 2, 3 => 3]
### Задача: Top K Frequent Elements 
<?php
declare(strict_types=1);

/**
 * @param int[] $nums
 * @return int[]
 */
function topKFrequent(array $nums, int $k): array
{
    $count = array_count_values($nums);

    // Bucket sort: index = frequency, value = list of numbers
    $buckets = array_fill(0, count($nums) + 1, []);

    foreach ($count as $num => $freq) {
        $buckets[$freq][] = $num;
    }

    $result = [];
    for ($i = count($buckets) - 1; $i > 0; $i--) {
        foreach ($buckets[$i] as $num) {
            $result[] = $num;
            if (count($result) === $k) {
                return $result;
            }
        }
    }

    return $result;
}

// nums = [1,1,1,2,2,3], k = 2
// count = [1=>3, 2=>2, 3=>1]
// buckets = [[], [3], [2], [1], [], [], []]
// Go from end: freq=3 -> 1, freq=2 -> 2
// Answer: [1, 2]
## Паттерн 3: Группировка (Group By)

Group Anagrams

<?php
declare(strict_types=1);

/**
 * @param string[] $strs
 * @return string[][]
 */
function groupAnagrams(array $strs): array
{
    $groups = [];

    foreach ($strs as $s) {
        // Key — sorted string (anagrams produce the same key)
        $chars = str_split($s);
        sort($chars);
        $key = implode('', $chars);
        $groups[$key][] = $s;
    }

    return array_values($groups);
}

// ["eat", "tea", "tan", "ate", "nat", "bat"]
// Keys: "aet" -> ["eat","tea","ate"]
//       "ant" -> ["tan","nat"]
//       "abt" -> ["bat"]
Альтернативный ключ через подсчёт символов (более эффективно): 
<?php
declare(strict_types=1);

/**
 * @param string[] $strs
 * @return string[][]
 */
function groupAnagramsV2(array $strs): array
{
    $groups = [];

    foreach ($strs as $s) {
        // Key — count of each letter
        $count = array_fill(0, 26, 0);
        for ($i = 0; $i < strlen($s); $i++) {
            $count[ord($s[$i]) - ord('a')]++;
        }
        $key = implode(',', $count);
        $groups[$key][] = $s;
    }

    return array_values($groups);
}
## Паттерн 4: Проверка изоморфизма / соответствия

Isomorphic Strings

<?php
declare(strict_types=1);

function isIsomorphic(string $s, string $t): bool
{
    if (strlen($s) !== strlen($t)) {
        return false;
    }

    $sToT = [];
    $tToS = [];

    for ($i = 0; $i < strlen($s); $i++) {
        $cs = $s[$i];
        $ct = $t[$i];

        if (isset($sToT[$cs])) {
            if ($sToT[$cs] !== $ct) {
                return false;
            }
        } else {
            $sToT[$cs] = $ct;
        }

        if (isset($tToS[$ct])) {
            if ($tToS[$ct] !== $cs) {
                return false;
            }
        } else {
            $tToS[$ct] = $cs;
        }
    }

    return true;
}

// "egg", "add" -> true  (e->a, g->d)
// "foo", "bar" -> false (o->a and o->r — conflict)
## Паттерн 5: Prefix Sum + HashMap

Уже разбирали в главе Prefix Sum, но это именно HashMap-паттерн.

<?php
declare(strict_types=1);

/**
 * @param int[] $nums
 */
function subarraySumEqualsK(array $nums, int $k): int
{
    $count = 0;
    $prefixSum = 0;
    $prefixMap = [0 => 1];

    foreach ($nums as $num) {
        $prefixSum += $num;
        if (isset($prefixMap[$prefixSum - $k])) {
            $count += $prefixMap[$prefixSum - $k];
        }
        $prefixMap[$prefixSum] = ($prefixMap[$prefixSum] ?? 0) + 1;
    }

    return $count;
}
## Паттерн 6: Longest Consecutive Sequence 
<?php
declare(strict_types=1);

/**
 * @param int[] $nums
 */
function longestConsecutive(array $nums): int
{
    $numSet = array_flip($nums); // O(1) lookup via isset
    $maxLength = 0;

    foreach ($numSet as $num => $_) {
        // Start only from the beginning of a sequence
        if (!isset($numSet[$num - 1])) {
            $current = $num;
            $length = 1;

            while (isset($numSet[$current + 1])) {
                $current++;
                $length++;
            }

            $maxLength = max($maxLength, $length);
        }
    }

    return $maxLength;
}

// nums = [100, 4, 200, 1, 3, 2]
// Set: {100, 4, 200, 1, 3, 2}
// 1 has no (1-1)=0 -> start: 1,2,3,4 -> length 4
// 100 has no 99 -> start: 100 -> length 1
// 200 has no 199 -> start: 200 -> length 1
// Answer: 4
**Сложность:** O(n) — каждый элемент проверяется максимум два раза.

Паттерн 7: Кеширование результатов

<?php
declare(strict_types=1);

// Memoization with HashMap
function fibonacci(int $n, array &$memo = []): int
{
    if (isset($memo[$n])) {
        return $memo[$n];
    }
    if ($n <= 1) {
        return $n;
    }
    $memo[$n] = fibonacci($n - 1, $memo) + fibonacci($n - 2, $memo);
    return $memo[$n];
}
## Сводная таблица паттернов
Паттерн Задача-пример Ключ HashMap Сложность
Complement search Two Sum значение -> индекс O(n)
Frequency count Top K Frequent элемент -> частота O(n)
Group by Group Anagrams sorted key -> list O(n*k)
Mapping Isomorphic Strings char -> char O(n)
Prefix + HashMap Subarray Sum = K prefix_sum -> count O(n)
Set membership Longest Consecutive Set lookup O(n)
Memoization Fibonacci input -> result varies

Запомни: HashMap превращает поиск из O(n) в O(1). Основные паттерны: 1) «Есть ли пара с суммой X?» — ищи complement. 2) «Сгруппировать по свойству» — используй свойство как ключ. 3) «Подсчитать подмассивы с суммой K» — prefix sum + HashMap. 4) «Найти последовательность» — Set для O(1) проверки.

Итоги

  1. Two Sum паттерн: complement = target - current
  2. Frequency Counter: подсчёт + bucket sort для Top K
  3. Group By: свойство как ключ, элементы как значения
  4. Prefix Sum + HashMap: подсчёт подмассивов за O(n)
  5. Set для O(1) проверки принадлежности

Проверь себя

Что вернёт subarraySumEqualsK для `nums = [1, 1, 1], k = 2`?

В функции longestConsecutive проверяется `!isset($numSet[$num - 1])`. Зачем?

Строки `"paper"` и `"title"` изоморфны (isIsomorphic). Почему нужны ДВА маппинга (sToT и tToS)?

В задаче Group Anagrams какой ключ HashMap эффективнее — отсортированная строка или подсчёт символов?

В задаче Two Sum `nums = [3, 2, 4], target = 6`. Какой ответ и почему HashMap эффективнее наивного решения?

Связанные темы

Паттерн Two Pointers

Связанная тема

Паттерны: Fast & Slow Pointers

Связанная тема

HashSet: уникальность и поиск

Связанная тема

Поиск в ширину BFS

Связанная тема

Kubernetes паттерны

Связанная тема