Skip to main content

Проверка наличия

Одним из самых распространенных применений хеш-таблицы или множества является определение наличия элемента за время O(1). Поскольку для массива это занимает O(n), использование хеш-таблицы или множества может значительно улучшить временную сложность алгоритма, обычно с O(n^2) до O(n).
Давайте рассмотрим несколько примеров задач.

Two sum​

https://leetcode.com/problems/two-sum/description/
Given an array of integers nums and an integer target, return indices of two numbers such that they add up to target. You cannot use the same index twice.

Наивное решение заключается в использовании вложенного цикла for для перебора каждой пары индексов и проверки, равна ли сумма target.
Это приведет к временной сложности O(n^2). В наивном решении первый цикл for фокусируется на числе num и выполняет второй цикл for, который ищет target - num в массиве. В массиве поиск target - num занимает O(n), но с хеш-таблицей это O(1).

Мы можем построить хеш-таблицу по мере прохождения массива, сопоставляя каждое значение с его индексом. На каждом индексе i, где num = nums[i], мы можем проверять нашу хеш-таблицу на наличие target - num. Добавление пар ключ-значение и проверка наличия target - num все занимают O(1), поэтому наша временная сложность улучшится до O(n).

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function (nums, target) {
  let map = new Map();
  for (let i = 0; i < nums.length; i++) {
    let num = nums[i];
    let complement = target - num;
    if (map.has(complement)) {
      return [i, map.get(complement)];
    }

    map.set(num, i);
  }

  return [-1, -1];
};

First Letter to Appear Twice​

https://leetcode.com/problems/first-letter-to-appear-twice/description/
Given a string s, return the first character to appear twice. It is guaranteed that the input will have a duplicate character.

Наивное решение заключалось бы в том, чтобы пройти по строке и для каждого символа c снова пройти по строке до символа c, чтобы увидеть, есть ли совпадение.

/**
 * @param {string} s
 * @return {character}
 */
var repeatedCharacter = function (s) {
  for (let i = 0; i < s.length; i++) {
    let c = s[i];
    for (let j = 0; j < i; j++) {
      if (s[j] == c) {
        return c;
      }
    }
  }

  return "";
};

Решение через set

/**
 * @param {string} s
 * @return {character}
 */
var repeatedCharacter = function (s) {
  let seen = new Set();
  for (const c of s) {
    if (seen.has(c)) {
      return c;
    }

    seen.add(c);
  }

  return " ";
};

Это улучшает нашу временную сложность до O(n), так как каждая итерация цикла for теперь выполняется за постоянное время.

Пространственная сложность представляет собой более интересную тему для обсуждения
Многие люди будут утверждать, что пространственная сложность равна O(1), потому что входные данные могут содержать только символы английского алфавита, что ограничено константой (26). Это очень распространено в задачах со строками и технически правильно. В условиях интервью это, вероятно, безопасный ответ, но также следует отметить, что пространственная сложность может быть O(m), где m - количество допустимых символов во входных данных. Это более обобщенный и также технически правильный ответ.

Задачи​