Алгоритм суммы двух чисел на JavaScript

Этот сценарий идеально отражает суть проблемы суммы двух чисел — классики в мире алгоритмических задач.

В статье рассмотрим два решения этой проблемы. Итак, давайте приступим!

Введение: Сумма двух чисел

Задача: Из массива целых чисел верните индексы двух чисел так, чтобы они складывались в определённое число. Например, если задано 10, а у нас есть массив [5, 1, 5, 3], то возвращаемое значение должно быть [0, 2], потому что индекс 0 — это 5, а индекс 2 — тоже 5, что в сумме даёт 10, целевое значение.

Эта задача может показаться простой, но она открывает двери для множества подходов, от перебора до более элегантных оптимизаций. Первое решение, приведённое ниже, выглядит несколько сомнительно, но не волнуйтесь, мы немного ускорим его во втором!

Решение 1: Танец грубой силы

Первый подход похож на классическое танцевальное движение — простое, но эффективное. Мы проверяем каждую возможную пару в массиве, чтобы узнать, совпадает ли их сумма с целью.

Давайте посмотрим на псевдокод, прежде чем погрузиться в решение.

// Итерация по каждому элементу
// Для каждого элемента выполняем итерацию по элементам, следующим за ним, например nums[j], где j > i.
// Если nums[i] + nums[j] === целевое значение
//// возвращаем индексы.

Попробуйте её решить, прежде чем продолжить!

function twoSum(nums, target) {
  for (let i = 0; i < nums.length; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === target) {
        return [i, j];
      }
    }
  }
  return null;
}

console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]

Теперь хочу спросить… Как вы считаете, этот алгоритм эффективен?

Что произойдёт, если на входе будет массив с миллионом или более элементов? В этом случае код может выполняться вечно.

Временная сложность, приведённого выше решения, составляет O(n^2). Можем ли сделать лучше? Конечно!

Давайте модернизируем код и сделаем его более эффективным с помощью хэш-карты.

Решение 2: Ускорение с помощью хэш-карты

Решение, которое собираюсь показать, использует хэш-карту для хранения индексов элементов. Хэш-карта (или хэш-таблица) — структура данных, хранящая пары ключ-значение и позволяющая быстро находить значения на основе ключей с помощью процесса, называемого хэшированием.

Таким образом, можно найти дополнение текущего элемента за постоянное время. (Смысл названия переменной complement заключается в том, что для любого заданного элемента nums[i] ищем другой элемент в массиве, сумма которых равна целевому значению. Этот другой элемент является дополнением/complement текущего элемента по отношению к целевой сумме).

И снова давайте начнём с псевдокода:

// Создаём пустую хэш-карту
// Итерация по каждому элементу nums[i]
// Вычисляем: complement = target - nums[i].
// если complement уже находится в хэш-карте:
//// возвращаем индексы [numToIndex[complement], i]
// добавляем nums[i] в хэш-карту с индексом i

Попробуйте её решить, прежде чем смотреть код!

function twoSumHashMap(nums, target) {
  const numToIndex = {};

  for (let i = 0; i < nums.length; i++) {
    const complement = target - nums[i];

    if (numToIndex[complement] !== undefined) {
      return [numToIndex[complement], i];
    }

    numToIndex[nums[i]] = i;
  }
  return null;
}
console.log(twoSumHashMap([2, 7, 11, 15], 9)); // [0, 1]

Этот алгоритм намного быстрее предыдущего, хотя и занимает дополнительное место для хэш-карты (сложность O(n)).

Однако поскольку необходимо выполнить эту проверку для каждого элемента массива, общая временная сложность всего алгоритма составляет O(n).

Заключение

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

Просили ли вас когда-нибудь решить этот алгоритм на собеседовании? Если да, напишите об этом. Также, если вы проводите собеседование и задавали этот вопрос, напишите, как справился кандидат.