Всем привет,

Вы ищете структуру данных, которая хранит уникальные значения, позволяет вставлять значения, определять общее количество значений и удалять значения? Идеальный выбор для этого – комплект. Многие языки программирования включают встроенную структуру данных Set, и JavaScript не является исключением. Давайте углубимся в то, как работают наборы.

Что установлено?
Set — это структура данных, которая позволяет хранить уникальные значения любого типа, будь то примитивные значения или ссылки на объекты. Набор позволяет выполнять операции вставки, удаления, обновления и изменения размера с временной сложностью O(1). Что делает установку более быстрой и эффективной.

Наборы созданы для быстрого доступа. Обычно они реализованы таким образом, что поиск элементов выполняется быстрее, чем простая проверка каждого элемента по одному. Типичной реализацией может быть хеш-таблица (поиск O(1)) или дерево поиска (поиск O(log(N))).

Ключевые моменты

• Быстрый доступ: наборы обеспечивают быстрый доступ к элементам.
• Реализация: обычно реализуется с использованием хеш-таблиц или деревьев поиска.
• Время поиска: среднее время поиска лучше, чем O(N), часто O(1) или O(log(N)).

Основные методы

1. add: добавит элемент в набор. Если элемент присутствует в наборе, он ничего не сделает.
2. has: возвращает true, если элемент присутствует в наборе, в противном случае — false.
3. size: вернет размер набора.
4. delete: элемент будет удален из набора.
5. keys : метод .keys() в наборе JavaScript возвращает новый объект-итератор, который содержит значения набора в том порядке, в котором они были вставлены.

Примеры

// 1. Create a new Set and use the .add() method to add elements
const mySet = new Set();
mySet.add(10);
mySet.add(20);
mySet.add(30);

console.log(mySet); // Output: Set { 10, 20, 30 }

// 2. Check if the Set has a specific element using .has() method
console.log(mySet.has(20)); // Output: true
console.log(mySet.has(40)); // Output: false

// 3. Delete an element from the Set using .delete() method
mySet.delete(20);
console.log(mySet); // Output: Set { 10, 30 }

// 4. Iterate over the Set using .keys() method
// In Sets, .keys() and .values() do the same thing
for (const key of mySet.keys()) {
  console.log(key);
}
// Output:
// 10
// 30

// 5. Get the size of the Set using .size property
console.log(mySet.size); // Output: 2

Пример набора с проблемой литкода:

3. Самая длинная подстрока без повторяющихся символов

Дана строка s. Найдите длину самой длинной подстроки без повторяющихся символов.

Решение

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    let set = new Set();
    let ans = 0;
    let s_index = 0;
    for (let i = 0; i 



Объяснение: 

Функция lengthOfLongestSubstring использует технику скользящего окна с набором для поиска самой длинной подстроки без повторяющихся символов: 

• Развернуть окно: добавьте персонажей в набор, если их еще нет.
• Сжать окно: удалять символы из начала окна при обнаружении дубликатов, регулируя размер окна.
• Длина обновления: отслеживание максимальной длины подстроки с уникальными символами.
• Этот подход обеспечивает эффективную временную сложность O(N) за счет обработки каждого символа не более двух раз.

Вот и все. Если у вас есть какие-либо сомнения, предложения или что-то еще, не стесняйтесь добавлять комментарии.

Источники:
МДН (набор)