Вам дан массив целых чисел. Напишите функцию, которая возвращает пару чисел, сумма которых равна нулю.

Можно предположить, что будет только одно решение. Каждый элемент массива можно использовать только один раз.

Пример:

Array of integers is [2, 7, 9, -2].
The pair that sums up to 0 is (2, -2).

Ввод:
список чисел, разделенных пробелом.

2 7 9 -2

Вывод:
2 числа из массива, сумма которых равна 0.
Мы отсортируем 2 числа для вас, чтобы вы могли легко сравнить их с ожидаемым результатом.

-2 2

Решение:

Наблюдать

  1. Для числа A мы хотим знать, существует ли такое число B, что A + B = 0.

Выводы:
метод грубой силы с двумя вложенными циклами for, один для поиска A, а другой для поиска B, должен решить проблему, но он крайне неэффективен при O(N² ) сложность.

2. Обратите внимание, что B = -A.

Полезная информация.
Вместо создания второго вложенного цикла for для поиска B мы можем использовать хэш-карту, чтобы быстро проверить, существует ли B в массиве.

Алгоритм

  1. Создайте пустую хэш-карту для хранения количества вхождений для каждого числа в массиве.
  2. Выполните итерацию по массиву.
    Для каждого числа A проверьте, присутствует ли -A в хэш-карте.
    Если да, верните пару (A, -A). В противном случае поместите A в хэш-карту.

Код

/**
 * @param {Array<Number>} nums
 * @param {Array<Number>} 2 numbers from nums that add up to 0.
 */
function pairOfZeroSum(nums) {
  const hashmap = new Map();
  for (let i = 0; i < nums.length; i++) {
    if (hashmap.has(-nums[i])) {
      return [nums[i], -nums[i]];
    }
    hashmap.set(nums[i], true);
  }
  // We should not reach this point since a solution is guaranteed
  // to exist.
  return [];
}

Анализ сложности

Мы посещаем каждое число в массиве только один раз. При каждом посещении мы вызываем пару функций хеш-карты, каждая из которых имеет сложность O(1).

Следовательно, общая сложность составляет O(N).