Если вы боретесь с алгоритмами, боитесь их или просто не знаете, с чего начать, эта статья для вас!

Вместе мы можем рассмотреть одну из самых распространенных «простых» задач на собеседовании: сумма двух. Существует множество вариантов этой проблемы, поэтому обязательно уточняйте у интервьюера точную формулировку/детали данного сценария и учитывайте любые потенциальные пограничные случаи (такие как пустой массив, повторяющиеся элементы, отрицательные числа или 0 и т. д.). . Ваш интервьюер оценит ваше мышление и может значительно помочь вам, предоставив вам больше информации. Я сосредоточусь на стандартном сценарии проблемы, который довольно снисходителен по своей формулировке и звучит примерно так:

"Учитывая непустой массив различных целых чисел и целевую сумму, вернуть массив из двух чисел (в любом порядке), которые в сумме составляют целевую сумму".

Небольшое примечание: иногда вам может быть предложен «реальный» сценарий, который на самом деле представляет собой замаскированную сумму двух вещей, что на самом деле произошло с моим другом. Его попросили рассмотреть набор фильмов разной продолжительности, общую продолжительность полета и написать алгоритм, который будет возвращать два разных фильма, длина которых в сумме равна продолжительности полета. Это классическая замаскированная сумма двух, и вы должны быть в состоянии быстро ее обнаружить.

Решение

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

Теперь я предоставлю один из возможных способов написания решения для хеш-карты, а затем объясню, почему он является наиболее эффективным из трех.

function twoSum(array, target) {
 let storage = {}  // declaring our storage hash
 for (const num of array) {
  const comp = target - num
 
  if (comp in storage) {
 
   return [comp, num]
 
  } else {
 
   storage[num] = true  // storing the integer in our hash
 
  }
 }
  
 return [] // if no match is found, return an empty array
}

Я думаю, что самая важная строка здесь — это первая строка внутри цикла for, где мы объявляем композицию const (сокращение от слова дополнение). Если у нас есть массив целых чисел, которые мы будем проходить одно за другим, чтобы найти нашу выигрышную пару, и у нас также есть целевая сумма, нам нужно знать, что нам нужно добавить к каждому целому числу в нашем массиве, чтобы составить сумма. Мы вычисляем это число, вычитая число (целое число в нашем массиве) из целевой суммы.

Теперь, когда у нас есть недостающая часть, нам нужно проверить наш (изначально пустой) хэш хранилища, который мы объявили в начале, чтобы увидеть, есть ли в нем наше целое дополнение. На самом первом уровне итерации, когда мы также просматриваем первое целое число в массиве, наш хэш хранилища пуст, поэтому мы сохраняем первое целое число как ключ со значением true. Мы делаем то же самое с каждым целым числом в массиве, ищем дополнение в нашем хэше, и если мы еще не сохранили его, мы сохраняем наше целое число в хеше и переходим к следующему целому числу в массиве. Наш хэш растет по мере того, как мы перемещаемся по массиву, используем хэш в качестве контрольной точки и заполняем его неудачными целыми числами, пока не пройдем весь массив. Если мы никогда не найдем наше дополнение после просмотра каждого целого числа в массиве, мы вернем пустой массив, чтобы показать, что нет двух различных целых чисел, которые в сумме дают цель. В этот момент у нас также будет каждое целое число из массива в нашем хэше хранилища.

Это помогает визуализировать процесс, который по существу состоит из двух шагов: вы начинаете с первого числа в массиве, проверяете изначально пустой хэш на наличие дополнения, затем сохраняете первое число в хеше. Затем вы смотрите на второе число в массиве и ищете дополнение в хеше, который в этот момент содержит первое (предыдущее) число. Если вы не можете найти дополнение в хеше, перейдите к третьему числу и повторяйте процесс, пока не найдете дополнение.

Это решение является наиболее оптимальным из-за характера хеш-карты как структуры данных. Если бы вы пошли по пути грубой силы, вы бы получили множество вложенных циклов, что было бы дорого. Маршрут бинарного поиска был бы излишне сложным (на мой взгляд) с большим количеством строк кода, а также более дорогостоящим, чем хеш-карта. В общем, я предлагаю использовать хэш всякий раз, когда вам нужно выполнить повторный поиск. Стоимость решения на основе хэш-карты составляет O(n) как для временной, так и для пространственной сложности, поскольку для этого требуется только проверка определенного места в памяти.

Я надеюсь, что это поможет вашему алгоритмическому путешествию!

Дополнительные материалы на plainenglish.io