Используя как грубую силу O (n ²), так и более элегантное линейное решение O (n)

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

Постановка задачи проста: для массива целых чисел вернуть индексы двух чисел так, чтобы они складывались в определенную цель. Мы можем предположить, что каждый вход будет иметь ровно одно решение, и мы не можем использовать элемент более одного раза. Итак, если наш массив равен [2, 7, 11, 15] с целевым значением 26, правильным результатом будет [2, 3], потому что элемент 2 (11) плюс элемент 3 (15) равняется 26. Давайте погрузимся в решения ниже.

Это первое решение называется методом грубой силы. Это называется грубой силой, потому что они, как правило, просты в применении и почти всегда найдут решение, если оно есть, попробовав все возможные ответы. Из-за этого они могут занять очень много времени. Вот первое решение:

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];
      }
    }
  }
}

Этот алгоритм берет массив (называемый nums) и перебирает его с вложенными циклами for. Вот что происходит на первой итерации в нашем примере:

  • i установлено в 0, j установлено в i + 1 (потому что мы знаем, что мы не можем использовать один и тот же элемент дважды)
  • Мы проверяем, выполняется ли наше условие: nums [0] + nums [1] = 26? 2 + 9 ≠ 26, поэтому мы продолжаем цикл, увеличивая j…
  • равно nums [0] + nums [2] = 26? 2 + 11 ≠ 26, поэтому мы продолжаем цикл, увеличивая j…
  • равно nums [0] + nums [3] = 26? 2 + 15 ≠ 26, поэтому мы продолжаем цикл, увеличивая i, когда мы достигли конца массива без решения, и начиная j с i + 1…
  • равно nums [1] + nums [2] = 26? 7+ 11 ≠ 26, продолжаем цикл…

Думаю, вы видите здесь закономерность. В конце концов, когда i = 2 и j = 3, оператор if вернет значение true и вернет эти позиции в виде массива.

Как видите, с массивом всего из 4 элементов требуется много итераций, чтобы найти решение. Фактически, потребуется число или размер элементов массива в квадрате! Минус 1, так как мы добавляем одну итерацию. Таким образом, временная сложность алгоритма составляет O (n ²). Это красная линия на графике ниже, и она занимает экспоненциально больше времени по сравнению со временем другого алгоритма, поскольку размер нашего массива увеличивается.

Это считается плохим. Можем ли мы сделать лучше? Давайте рассмотрим решение за O (n) ниже.

function twoSum(nums, target) {
let numObj = {};
  for (let i = 0; i < nums.length; i++) {
    let complement = target - nums[i];
    if (numObj[complement] !== undefined) {
      return [numObj[complement], i];
    }
    numObj[nums[i]] = i;
  }
}

Обычно, когда мы сравниваем парадигму одного алгоритма с другим, приходится искать компромисс. В этом случае компромисс - пространство. Чтобы ускорить работу, я создам в памяти новый объект. Мы инициализируем объект или хеш-карту, называемую numObj. Затем мы выполняем итерацию, как и раньше, но только один раз и с дополнительной переменной под названием «дополнение». Это будет число, которое я должен был видеть раньше, и если его добавить к числу, которое я сейчас повторяю, он будет равен целевому. Давайте пройдемся по нему с помощью нашего массива: [2, 7, 11, 15]

  • Когда i = 0, дополнение будет 26 - nums [0], или 26–2 = 24.
  • Затем происходит интересное. Алгоритм спрашивает, не является ли это число (24) неопределенным в numObj. Другими словами, видели ли мы это раньше и существует ли в этом объекте ключ? Поскольку мы не видели этого раньше, выражение if принимает значение false, и мы продолжаем.
  • Затем мы добавляем nums [i], равное 2, со значением 0 в numObj, которое было индексом, который он имел в массиве.
  • Когда i = 1, дополнение будет 26 - nums [1], или 26–7 = 19.
  • 19 не определено в numObj? Это так, поэтому мы добавляем его с ключом 7 (элемент в массиве) и значением 1 (индекс 7 в массиве).
  • Когда i = 2, дополнение будет 26 - nums [2], или 26–11 = 15.
  • 15 undefined в numObj? Это так, поэтому мы добавляем его с ключом 11 (элемент в массиве) и значением 2 (индекс 11 в массиве).
  • Когда i = 3, дополнение будет 26 - nums [3], или 26–15 = 11.
  • 11 не определено в numObj? Это нет. Мы видели это в предыдущей итерации. Теперь выражение оценивается как истинно. Итак, мы возвращаем значение ключа 11 в numObj, которое равно 2, вместе с i, которое равно 3. И это наш ответ.

Хотя его сложнее осмыслить, вы видите, что этот алгоритм требует гораздо меньше итераций. Фактически, в худшем случае, ровно столько итераций, сколько размер массива, что дает нам время O (n), или синюю линию на графике выше. Намного лучше!

Спасибо за прочтение!

И помните: выдержка ›талант.