Вступление

В этом посте я хочу рассмотреть two-sum вопрос который можно встретить на собеседованиях, поскольку он имеет как прямое решение перебором, так и логическое решение более эффективное по времени, с помощью которого можно продемонстрировать понимание основ информатики. Мы рассмотрим оба возможных решения и, я надеюсь, вы узнаете что нибудь новое!

Two-Sum вопрос

Во-первых, давайте разберемся с вопросом. Обычно его озвучивают как то так:

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

/**
 * @param {number[]} nums
 * @param {number} total
 * @return {number[]}
 */
const twoSum = (arr, total) => {
  // Solution here
};

Как правило, обычно приводиться пару примеров допустимых комбинаций ввода/вывода:

input: nums = [1, 2, 3], total = 4
output: [1, 3]

input: nums = [3, 9, 12, 20], total = 21
output: [9, 12]

Краткое примечание про написание кода во время интервью

Если во время собеседования вам предложено написать какой либо код, было бы разумно задать несколько уточняющих вопросов, прежде чем приступить к решению проблемы. В случае с вопросом Two-Sum вы можете задать следующие вопросы (и, возможно, некоторые другие, которые я не смог придумать):

• Может ли nums быть чем-то другим, кроме массива чисел?
• Может ли total быть чем-то другим, кроме числа?
• Всегда будет два числа в nums, которые в сумме будут равны total? Если нет, то каким должен быть вывод, когда нет решения?

Для этого поста в блоге мы будем предполагать, что nums всегда будет массивом чисел, total всегда будет числом, и всегда будет решение проблемы (т. е. два числа в nums всегда будут складываться в total ).

Решение прямым перебором (Brute Force)

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

• начать с первого элемента nums и перебрать каждый из оставшихся элементов массива, проверяя, суммируются ли они до total
• далее если ответ не найден перейти ко второму элементу nums и перебрать каждый из оставшихся элементов, проверяя, составляют ли они в сумме total
• повторять, пока не будет найдена соответствующая сумма!

В коде мы реализуем это как вложенный цикл:

/**
 * @param {number[]} nums
 * @param {number} total
 * @return {number[]}
 */
const twoSum = (nums, total) => {
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      if (nums[i] + nums[j] === total) {
        return [nums[i], nums[j]];
      }
    }
  }
};

console.log(twoSum([1, 2, 3], 4)); // [1, 3]
console.log(twoSum([3, 9, 12, 20], 21)); // [9, 12]

Потрясающие! Есть несколько потенциально сложных аспектов этого решения; давайте быстро разберем их.

Почему внешний цикл останавливается на i < nums.length — 1?

Внешний цикл не должен учитывать последний элемент массива nums, только второй-последний элемент массива. Так как вложенный цикл всегда будет учитывать последний элемент.

Почему вложенный цикл начинается с j = i + 1?

Как мы описали выше, внешний цикл начинается с одной позиции в массиве, и внутренний цикл должен начинаться только с чисел, встречающихся позже в массиве. Любые комбинации, включая более ранние числа в массиве, были проверены ранее.

Проблема подхода с перебором

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

Так в чем проблема? Вложенные циклы имеют алгебраическую сложность O(n²).

Понимание сложности O(n²)

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

Давайте проведем эксперимент. Мы создадим массив из 100 000 элементов, причем решающими номерами будут последние два элемента.

const len = 100000;
const bigArr = new Array(len).fill(1);
bigArr[len - 2] = 9;
bigArr[len - 1] = 10;
const total = 19;

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

const twoSum = (nums, total) => {
  let iterations = 0;
  const startTime = new Date();
  for (let i = 0; i < nums.length - 1; i++) {
    for (let j = i + 1; j < nums.length; j++) {
      iterations++;
      if (nums[i] + nums[j] === total) {
        console.log(
          `Iterations: ${iterations}`,
          `Time: ${new Date() - startTime}ms`
        );
        return [nums[i], nums[j]];
      }
    }
  }
};

twoSum(bigArr, total);
// Iterations: 4999950000 Time: 20032ms

Решение для перебора прошло почти 5 миллиардов итераций, и на моем компьютере это заняло 20 секунд. Ужас! Посмотрим, сможем ли мы сделать лучше.

Сила объектов (и, что более важно, хеш-таблицы)

Мы можем, на самом деле, сделать лучше. Вместо того, чтобы создавать вложенный цикл, давайте просто один раз пройдемся по массиву nums. Чтобы отслеживать элементы массива, которые мы уже проверили, мы собираемся добавить их в качестве ключей к объекту. Для каждого элемента массива мы проверяем, существует ли дополнительный ключ в нашем объекте.

Вот пример кода!

const twoSum = (nums, total) => {
  // Keep track of previous array values
  const previousValues = {};

  for (let i = 0; i < nums.length; i++) {
    // What previous value needs to exist for
    // us to have found our solution?
    const complement = total - nums[i];

    if (previousValues[complement]) {
      return [complement, nums[i]];
    }

    // This current array item now becomes
    // a previous value
    previousValues[nums[i]] = true;
  }
};

console.log(twoSum([1, 2, 3], 4)); // [1, 3]
console.log(twoSum([3, 9, 12, 20], 21)); // [9, 12]

Возможно, вы спросите: у нас есть только один цикл, конечно, но наш второй цикл заменен этим поиском previousValues[complement]. Это действительно намного эффективнее, чем второй цикл?

Ответ — да, потому что поиск по объекту — имеет сложность O(1). Это связано с использованием JavaScript хеш-таблиц в объектах! Отличный учебник по хеш-таблицам описан в этом прекрасном посте.

Поскольку поиск объекта равен O(1), а первый цикл равен O(n), сложность нашей функции теперь равна O(n). Давайте попробуем наш новый алгоритм на том же большом массиве, который мы использовали ранее.

const len = 100000;
const bigArr = new Array(len).fill(1);
bigArr[len - 2] = 9;
bigArr[len - 1] = 10;
const total = 19;

const twoSum = (nums, total) => {
  let iterations = 0;
  const startTime = new Date();

  const previousValues = {};
  for (let i = 0; i < nums.length; i++) {
    iterations++;
    const complement = total - nums[i];
    if (previousValues[complement]) {
      console.log(
        `Iterations: ${iterations}`,
        `Time: ${new Date() - startTime}ms`
      );
      return [complement, nums[i]];
    }
    previousValues[nums[i]] = true;
  }
};

twoSum(bigArr, total);
// Iterations: 100000 Time: 4ms

Теперь все работает гораздо быстрее.

Ничто не бесплатно

Хотя мы уменьшили нашу сложность алгоритма, мы увеличили нашу пространственную сложность, поскольку нам теперь нужно создавать новый объект previousValues в памяти. Для очень больших объектов (например, порядка миллиона элементов) речь будет идти о 10 МБ памяти и более. Но этот выбор за вами!

Оригинальная статья Nick Sciall: Exploring the Two-Sum Interview Question in JavaScript