Поиск пары элементов массива, дающих заданную сумму

Условие

Дан набор чисел. Требуется написать функцию, которая проверяет, существует ли в этом наборе два элемента, сумма которых равна заданному значению. Решение должно работать за O(n) по времени и O(n) по памяти.

 const hasPairWithSum = (numbers, target) => {}

hasPairWithSum([3, 4, 7, 10], 8); // false
hasPairWithSum([1, 4, 4, 9], 8); // true
hasPairWithSum([-8, 1, 4, 9, 16], 8); // true

Ответ

Храните уже просмотренные числа в Set и для каждого x проверяйте target − x. Проверка до добавления x не позволяет использовать одну позицию дважды.

function hasPairWithSum(numbers, target) {
  const seen = new Set();
  for (const value of numbers) {
    if (seen.has(target - value)) return true;
    seen.add(value);
  }
  return false;
}

Для [4] и суммы 8 ответ false, для [4,4] — true. Отрицательные числа обрабатываются тем же алгоритмом. Для безопасных целых нет проблемы неточного сравнения дробей; произвольные Number требуют учитывать точность. Ожидаемое время O(n), память O(n) при стандартном поведении Set.