Mid💻Практика6 min

Паттерны с HashMap

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

AlgoHash tables

Паттерны с HashMap

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

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

PHPGo
<?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]

func twoSum(nums []int, target int) []int {
	seen := map[int]int{} // value -> index

	for i, num := range nums {
		complement := target - num
		if j, ok := seen[complement]; ok {
			return []int{j, i}
		}
		seen[num] = i
	}

	return nil
}

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

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

PHPGo
<?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]

func frequencyCount(arr []int) map[int]int {
	freq := map[int]int{}
	for _, x := range arr {
		freq[x]++
	}
	return freq
}

// frequencyCount([]int{1, 2, 2, 3, 3, 3})
// map[1:1  2:2  3:3]
### Задача: Top K Frequent Elements
PHPGo
<?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]

func topKFrequent(nums []int, k int) []int {
	count := map[int]int{}
	for _, num := range nums {
		count[num]++
	}

	// Bucket sort: index = frequency, value = list of numbers
	buckets := make([][]int, len(nums)+1)
	for num, freq := range count {
		buckets[freq] = append(buckets[freq], num)
	}

	result := []int{}
	for i := len(buckets) - 1; i > 0; i-- {
		for _, num := range buckets[i] {
			result = append(result, num)
			if len(result) == k {
				return result
			}
		}
	}

	return result
}

// nums = [1,1,1,2,2,3], k = 2
// Answer: [1, 2]
## Паттерн 3: Группировка (Group By)

Group Anagrams

PHPGo
<?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"]

import "sort"

func groupAnagrams(strs []string) [][]string {
	groups := map[string][]string{}

	for _, s := range strs {
		// Key — sorted string (anagrams produce the same key)
		chars := []byte(s)
		sort.Slice(chars, func(i, j int) bool { return chars[i] < chars[j] })
		key := string(chars)
		groups[key] = append(groups[key], s)
	}

	result := make([][]string, 0, len(groups))
	for _, group := range groups {
		result = append(result, group)
	}
	return result
}

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

func groupAnagramsV2(strs []string) [][]string {
	groups := map[[26]int][]string{}

	for _, s := range strs {
		// Key — count of each letter (array is comparable in Go)
		var count [26]int
		for i := 0; i < len(s); i++ {
			count[s[i]-'a']++
		}
		groups[count] = append(groups[count], s)
	}

	result := make([][]string, 0, len(groups))
	for _, group := range groups {
		result = append(result, group)
	}
	return result
}
## Паттерн 4: Проверка изоморфизма / соответствия

Isomorphic Strings

PHPGo
<?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)

func isIsomorphic(s, t string) bool {
	if len(s) != len(t) {
		return false
	}

	sToT := map[byte]byte{}
	tToS := map[byte]byte{}

	for i := 0; i < len(s); i++ {
		cs, ct := s[i], t[i]

		if mapped, ok := sToT[cs]; ok {
			if mapped != ct {
				return false
			}
		} else {
			sToT[cs] = ct
		}

		if mapped, ok := tToS[ct]; ok {
			if mapped != 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-паттерн.

PHPGo
<?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;
}

func subarraySumEqualsK(nums []int, k int) int {
	count := 0
	prefixSum := 0
	prefixMap := map[int]int{0: 1}

	for _, num := range nums {
		prefixSum += num
		if v, ok := prefixMap[prefixSum-k]; ok {
			count += v
		}
		prefixMap[prefixSum]++
	}

	return count
}
## Паттерн 6: Longest Consecutive Sequence
PHPGo
<?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

func longestConsecutive(nums []int) int {
	numSet := map[int]bool{}
	for _, num := range nums {
		numSet[num] = true
	}

	maxLength := 0

	for num := range numSet {
		// Start only from the beginning of a sequence
		if !numSet[num-1] {
			current := num
			length := 1

			for numSet[current+1] {
				current++
				length++
			}

			if length > maxLength {
				maxLength = length
			}
		}
	}

	return maxLength
}

// nums = [100, 4, 200, 1, 3, 2]
// Answer: 4
**Сложность:** O(n) — каждый элемент проверяется максимум два раза.

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

PHPGo
<?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];
}

// fibonacci uses memoization with a map.
func fibonacci(n int, memo map[int]int) int {
	if v, ok := memo[n]; ok {
		return v
	}
	if n <= 1 {
		return n
	}
	memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo)
	return memo[n]
}

// Usage: fibonacci(10, map[int]int{})
## Сводная таблица паттернов
Паттерн Задача-пример Ключ 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 эффективнее наивного решения?

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

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

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

Kubernetes паттерны

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

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

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