re:re:actable
Урок 031 минута чтения

Как использовать Set?

На этой странице
Кратко

Set хранит уникальные значения и используется для проверки принадлежности, удаления дублей, visited-множества в графах и задач на пересечение/объединение.

Вопрос

Как использовать Set для уникальности и быстрой проверки наличия?

Базовый API

const seen = new Set<number>()
 
seen.add(10)
seen.add(20)
 
console.log(seen.has(10))
console.log(seen.delete(20))
console.log(seen.size)

Удаление дублей

function unique(nums: number[]): number[] {
  return [...new Set(nums)]
}

Time O(n), space O(n).

Проверка повторов

function hasDuplicate(nums: number[]): boolean {
  const seen = new Set<number>()
 
  for (const num of nums) {
    if (seen.has(num)) return true
    seen.add(num)
  }
 
  return false
}

Visited в графе

function dfs(node: string, graph: Map<string, string[]>, visited = new Set<string>()) {
  if (visited.has(node)) return
 
  visited.add(node)
 
  for (const next of graph.get(node) ?? []) {
    dfs(next, graph, visited)
  }
}

Что отвечать на собеседовании?

Set - коллекция уникальных значений. В алгоритмах он нужен, когда нужно быстро проверять, встречали ли мы значение раньше: duplicates, membership, visited в графах, пересечения множеств. По смыслу Set хранит только ключи, а Map хранит ключ-значение.

Что важно помнить: частые ошибки

  • Использовать Array.includes внутри цикла вместо Set.has.
  • Забывать, что объекты сравниваются по ссылке.
  • Использовать Set, когда нужно хранить счетчик, а не факт наличия.
  • Думать, что Set автоматически сортирует значения.
  • Мутировать объект после добавления и ожидать value equality.

Мини-шпаргалка

  • add - добавить.
  • has - проверить.
  • delete - удалить.
  • size - размер.
  • Unique values - new Set(arr).
  • visited в DFS/BFS - почти всегда Set.

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

MDN: Set.

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

Поиск

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