Урок 042 минуты чтения
Как использовать hash map для частот и индексов?
На этой странице
Кратко
Hash map через Map часто превращает перебор O(n^2) в O(n): можно хранить частоты, последние индексы, нужные complement-значения, prefix sums и связи graph adjacency list.
Вопрос
Как использовать hash map для подсчета частот и хранения индексов?
Частоты
function countChars(s: string): Map<string, number> {
const count = new Map<string, number>()
for (const char of s) {
count.set(char, (count.get(char) ?? 0) + 1)
}
return count
}Индексы
function firstRepeated(nums: number[]): number | null {
const firstIndex = new Map<number, number>()
for (let i = 0; i < nums.length; i++) {
if (firstIndex.has(nums[i])) return nums[i]
firstIndex.set(nums[i], i)
}
return null
}Complement
function hasPair(nums: number[], target: number): boolean {
const seen = new Set<number>()
for (const num of nums) {
if (seen.has(target - num)) return true
seen.add(num)
}
return false
}Когда узнавать паттерн?
- нужно быстро проверять "видели ли";
- нужно считать количество;
- нужно найти пару/группу;
- анаграммы;
- duplicates;
- prefix sum;
- graph adjacency list.
Что отвечать на собеседовании?
Hash map используется, когда нужно быстро получить информацию по ключу: частоту, индекс, наличие, список соседей или число предыдущих prefix sums. В JS чаще всего это Map, а если нужно только наличие - Set. Обычно мы платим O(n) памяти, чтобы уменьшить время до O(n).
Что важно помнить: частые ошибки
- Не обновлять счетчик.
- Проверять truthy вместо
has. - Забывать порядок: сначала проверить complement, потом добавить текущий элемент.
- Использовать object для нестроковых ключей.
- Не учитывать space complexity.
Мини-шпаргалка
- Частоты ->
Map<T, number>. - Наличие ->
Set<T>. - Индекс ->
Map<T, number>. - Complement ->
target - x. - Prefix count ->
Map<number, number>. - Память обычно
O(n).
Документация
Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.