re:re:actable
Урок 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).

Документация

MDN: Map, LeetCode: Hash Table problems.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам