02 · БЫСТРЫЙ ДОСТУП

Хеш-таблицы

В Go встроенная map закрывает задачи на частоты, множества и индексы.

3 Go-примитива3 примераInterview 150

СНАЧАЛА ИНСТРУМЕНТЫ

Примитивы Go

Минимальный синтаксис, который понадобится в решении.

Map

m := make(map[string]int)
m["go"]++
value, ok := m["go"]
delete(m, "go")

Поиск и вставка в среднем O(1); порядок обхода не определён.

Set

seen := make(map[int]struct{})
seen[42] = struct{}{}
_, exists := seen[42]

struct{} не занимает места под значение.

Счётчик

freq := map[rune]int{}
for _, ch := range text {
    freq[ch]++
}

Частоты часто превращают вложенный поиск O(n²) в O(n).

ПРАКТИКА

Примеры решений

Три идиоматичных решения на Go с оценкой времени и памяти.

ПРИМЕР РЕШЕНИЯ

Two Sum

Храним индекс уже увиденного дополнения.

O(n) time · O(n) space

solution.go

func twoSum(nums []int, target int) []int {
    seen := make(map[int]int)
    for i, n := range nums {
        if j, ok := seen[target-n]; ok {
            return []int{j, i}
        }
        seen[n] = i
    }
    return nil
}

ПРИМЕР РЕШЕНИЯ

Группировка анаграмм

Массив частот становится сравнимым ключом map.

O(n · k) time · O(n · k) space

solution.go

func groupAnagrams(words []string) [][]string {
    groups := map[[26]int][]string{}
    for _, word := range words {
        var key [26]int
        for _, ch := range word { key[ch-'a']++ }
        groups[key] = append(groups[key], word)
    }
    out := make([][]string, 0, len(groups))
    for _, group := range groups { out = append(out, group) }
    return out
}

ПРИМЕР РЕШЕНИЯ

Содержит дубликат

Множество мгновенно показывает, встречалось ли значение раньше.

O(n) time · O(n) space

solution.go

func containsDuplicate(nums []int) bool {
    seen := make(map[int]struct{}, len(nums))
    for _, n := range nums {
        if _, ok := seen[n]; ok { return true }
        seen[n] = struct{}{}
    }
    return false
}

ПЕРЕД КОДОМ

Чек-лист рассуждения

Используй comma-ok, если нулевое значение допустимо
Не полагайся на порядок range
Оцени память: map хранит до O(n) ключей