«Я это уже видел?» за один шаг

Tier 1Бесплатно

Elman HuseynovОбновлено 2026-10-21

Уровень

Где применяется

1. Задача

У тебя список ID пользователей. Нужно узнать, встречается ли какой-нибудь ID дважды. Первое, что приходит в голову: взять каждый ID и сравнить его со всеми остальными. Для короткого списка это нормально. Для миллиона ID это миллион на миллион сравнений, та самая ловушка O(n²) из урока про Big-O.

Есть приём, который отвечает на вопрос «я это уже видел?» примерно за один шаг, каким бы большим ни был список. Он требует лишней памяти. Этот обмен памяти на скорость и есть тема урока.

2. Простыми словами

Возьми тестовый список id: a, b, a. Если сравнивать каждую пару, то надо проверить a с b, a с a и b с a. Для трёх id это 3 сравнения. Для миллиона id это около 500 миллиардов.

Вместо этого по ходу прохода веди набор уже встреченных id. Читаешь a: набор пуст, добавляешь a. Читаешь b: его в наборе нет, добавляешь. Читаешь a: он уже в наборе, значит, a это повтор. На каждый вопрос хватило одного взгляда в набор, а список ты прочитал один раз.

Иногда хватает отметки «уже встречал», как здесь. Иногда нужно знать, сколько раз встретилось каждое значение, и тогда рядом с каждым значением хранится счётчик. Для типов событий x, x, y в конце получится x: 2, y: 1. В обоих случаях один быстрый взгляд отвечает на вопрос, какой бы длинным ни был список.

3. Идея

Нужны два инструмента, оба встроены в JavaScript.

Set это мешок уникальных значений (каждое лежит один раз). Можно спросить seen.has(x), то есть «x уже в мешке?», и ответ придёт примерно за один шаг. Ты проходишь список один раз. Перед тем как взять значение, проверяешь мешок. Если значение там, ты нашёл повтор. Если нет, кладёшь его в мешок через seen.add(x).

Map это набор пар ключ → значение. Им удобно считать: для каждого элемента записываешь его счётчик как «старое значение плюс один». Ключ, которого ещё нет, считается за ноль. Поэтому текущий счёт даёт counts.get(k) ?? 0. Знак ?? значит «если слева ничего нет, возьми то, что справа».

Проследим подсчёт на ["a", "b", "a"]. Видим a: счёта для a ещё нет, это 0, плюс один, получаем {a:1}. Видим b: получаем {a:1, b:1}. Снова видим a: было 1, стало 2, получаем {a:2, b:1}. Теперь проверка на повтор в [3, 1, 3]. Видим 3: в мешке его нет, кладём. Видим 1: нет, кладём. Видим 3: он уже в мешке, повтор найден. Каждой задаче хватает одного прохода.

4. Во что это обходится

Время O(n): один проход, и каждая проверка или обновление занимает примерно один шаг. Память O(n): в худшем случае все значения разные, и все попадают в структуру. Эта память и есть цена. Ты платишь O(n) лишней памяти и вместо вложенного прохода за O(n²) получаешь один проход за O(n). В уроке про перестановку массива на месте было наоборот: там ты экономил память до O(1). Когда список большой, обмен памяти на скорость обычно оправдан.

Бери Map, а не обычный объект, в трёх случаях: ключи это числа, важен порядок добавления или ключ может совпасть со встроенным именем вроде "constructor".

5. Где это встречается

Идемпотентность и поиск повторов: этот ID запроса или сообщения уже обработан? Если да, второй раз его не выполняют. Сводки метрик по эндпоинту (адресу, на который приходят запросы) или по коду ответа. Удаление повторяющихся событий из потока. Подсчёт уникальных пользователей. Когда записи из потока сводят по ключу, первым выбором будет Map. Для проверки «это уже видели» первым выбором будет Set. В этом курсе ты будешь пользоваться ими постоянно.

Первое повторяющееся число через Set

firstDuplicate([3, 8, 1, 5, 8, 3])

arr

seen (Set: числа, которые уже встречались)

пусто

return = ?

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

1 / 7

Гонка скорости

Два вложенных цикла и хеш-множество ищут повтор в одних и тех же 40 числах

Столбики: числа. Повторяется только последнее.

Одна операция: одно сравнение или одна проверка либо вставка в хеш-множество. За каждый кадр все дорожки делают одинаковое число операций, поэтому медленная отстаёт.

Два вложенных цикла O(n²)

операций: 0

Хеш-множество O(n)

операций: 0

А если чисел больше

Операции для n чисел и примерное время при 100 миллионах простых операций в секунду. Это оценка по тому же счёту, а не замер.

n = 1 000

Два вложенных цикла462,2 тыс. · 4,6 мс

Хеш-множество2 тыс. · меньше 1 мс

n = 100 000

Два вложенных цикла4,6 млрд · 46 с

Хеш-множество200 тыс. · 2 мс

n = 10 000 000

Два вложенных цикла46,2 трлн · 5,3 дн.

Хеш-множество20 млн · 200 мс

Как узнать

Хеш-множество / словарь (Hash set / map)

Эти слова в условии значат этот паттерн

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

Похоже, но не то

Два указателя (с концов) (Two pointers (opposite ends))
Двум указателям нужен отсортированный массив, зато лишней памяти нет. Хеш нужен, когда сортировать нельзя.
Скользящее окно (переменное) (Sliding window (variable))
Окно отвечает на вопрос про один непрерывный отрезок. У словаря понятия отрезка нет вообще.
Сортировка без сравнений (подсчётом / поразрядная) (Non-comparison sort (counting / radix))
Сортировка подсчётом тоже считает частоты, но ей нужны маленькие целые ключи. Словарь берёт любой ключ.
Trie (префиксное дерево) (Trie (prefix tree))
Trie делит общие префиксы, поэтому отвечает на запросы по префиксу. Словарь сравнивает только целые ключи.
Префиксные суммы (Prefix sums)
Префиксные суммы отвечают про диапазоны в исходном порядке. Хеш порядок не хранит.

n до 1e6 неотсортированных значений даёт O(n) времени. Память O(n), потому что хранится каждый ключ.

На LeetCode

Задачи, где нужно понять, встречалось ли значение раньше, или сколько раз встречается каждое значение. Один проход с Set или со счётчиком в Map заменяет цикл внутри цикла.

1.Two Sum (откроется в новой вкладке)Лёгкая
Храни каждое число с его индексом, а перед записью ищи в Map число target минус текущее.
242.Valid Anagram (откроется в новой вкладке)Лёгкая
Посчитай буквы одного слова, вычти буквы другого, и все счётчики должны вернуться к 0.
387.First Unique Character in a String (откроется в новой вкладке)Лёгкая
Сначала посчитай все буквы, потом пройди ещё раз и найди первую букву со счётчиком 1.
1679.Max Number of K-Sum Pairs (откроется в новой вкладке)Средняя
Храни счётчик чисел, которые ждут пару, и соединяй каждое новое число с ожидающим числом k минус текущее.

Твоя задача (Tier 1)

Напиши две функции: countEventTypes(records) и findDuplicateIds(records).

Инструмент выбирай по вопросу. Посчитать, сколько раз что-то встречается: Map. Проверить, было ли что-то раньше: Set.

Вход: records, список записей, у каждой есть type и id.
countEventTypes возвращает карту: каждому type соответствует число его появлений.
findDuplicateIds возвращает список id, которые встречаются больше одного раза. Каждый такой id в списке один раз.

Шаги:

Для countEventTypes: заведи пустую карту counts. Для каждой записи прибавь 1 к счёту под её type (в первый раз считай от 0). Верни counts.
Для findDuplicateIds: заведи пустое множество seen и пустой список-ответ. Для каждой записи: если её id уже есть в seen, это повтор. Добавь id в ответ, если ещё не добавлял его раньше. Если id в seen нет, положи его туда. Верни ответ.

Готово, когда проходят все тесты:

countEventTypes:

[{id:"a",type:"x"}, {id:"b",type:"x"}, {id:"a",type:"y"}] -> x: 2, y: 1
[{id:"a",type:"x"}, {id:"b",type:"y"}, {id:"c",type:"z"}] -> x: 1, y: 1, z: 1
[] -> пустая карта

findDuplicateIds:

[{id:"a"}, {id:"b"}, {id:"a"}] -> ["a"]
[{id:"a"}, {id:"b"}, {id:"c"}] -> [] (все id разные)
[{id:"a"}, {id:"a"}, {id:"a"}] -> ["a"] (повторяющийся id указан один раз)
[] -> []

Практика

countEventTypes / findDuplicateIds

export function countEventTypes(records) {
  // Your code here. The task is described in the box above the editor.
}

export function findDuplicateIds(records) {
  // Your code here. The task is described in the box above the editor.
}

Ты здесь как гость

Тесты запускаются прямо здесь, без аккаунта. Код сохраняется только в этом браузере. Бесплатный аккаунт сохранит его на любом устройстве, отметит шаг пройденным и покажет, где ты в курсе.

Завести бесплатный аккаунт Войти

Лестница подсказок

Застрял? Открывай по одной, но сначала попробуй сам.

НазадЗаполненность и расширение таблицы ДалееСходимся с двух концов