Поиск пары чисел с заданной суммой

Наивное решение «в лоб» с двумя вложенными циклами будет иметь квадратичную сложность O(n²), что не удовлетворяет условию. Чтобы достичь линейной сложности O(n), нужно избежать вложенных циклов.

Подумайте, как можно запоминать уже просмотренные числа, чтобы для каждого нового числа быстро проверять, встречалось ли нам ранее «дополнение» до нужной суммы. Какая структура данных позволяет делать проверку на наличие элемента за константное время O(1)?

const hasPairWithSum = (arr, sum) => {
  // Создаем Set для хранения чисел, которые мы уже видели.
  // Set обеспечивает очень быстрый поиск (в среднем O(1)).
  const seenNumbers = new Set();
 
  // Проходим по каждому числу в исходном массиве.
  for (const num of arr) {
    // Для каждого числа `num` вычисляем "дополнение" (`complement`),
    // то есть число, которое в сумме с `num` даст `sum`.
    const complement = sum - num;
 
    // Проверяем, есть ли это "дополнение" в нашем Set'е.
    // Если да, значит, мы нашли пару.
    if (seenNumbers.has(complement)) {
      return true; // Пара найдена, немедленно выходим из функции.
    }
 
    // Если "дополнение" не найдено, добавляем текущее число `num` в Set.
    // Это нужно, чтобы последующие числа могли "найти" его в качестве своего дополнения.
    seenNumbers.add(num);
  }
 
  // Если мы прошли весь массив и не нашли ни одной пары,
  // значит, ее нет. Возвращаем false.
  return false;
};

Почему именно так:

• Линейная сложность O(n): Мы проходим по массиву всего один раз.
• Set для скорости: Операции добавления (add) и проверки наличия (has) в Set в среднем выполняются за константное время O(1). Это позволяет нам для каждого элемента массива мгновенно проверять, встречали ли мы уже число, которое в сумме с текущим даст sum.
• Логика: Для каждого числа num из массива мы вычисляем, какое число complement нам нужно, чтобы получить sum. Затем мы проверяем, есть ли complement в нашем Set’е. Если да — мы нашли пару, и можно возвращать true. Если нет — добавляем текущее число num в Set и переходим к следующему элементу. Если мы прошли весь массив и не нашли пару, возвращаем false.
• Пространственная сложность: O(n) в худшем случае, так как Set может хранить все элементы массива.

const hasPairWithSum = (arr, sum) => {
  // Сортируем массив. Сложность O(n log n)
  const sortedArr = [...arr].sort((a, b) => a - b);
  
  let left = 0;
  let right = sortedArr.length - 1;
 
  // Проходим по массиву с двух концов. Сложность O(n)
  while (left < right) {
    const currentSum = sortedArr[left] + sortedArr[right];
 
    if (currentSum === sum) {
      return true; // Нашли пару
    } else if (currentSum < sum) {
      left++; // Сумма слишком мала, двигаем левый указатель вправо
    } else {
      right--; // Сумма слишком велика, двигаем правый указатель влево
    }
  }
 
  return false; // Пара не найдена
};

Почему именно так:

• Идея: Если массив отсортирован, можно эффективно проверять суммы, двигаясь с двух концов навстречу друг другу.
• Временная сложность O(n log n): Определяется в основном сортировкой. Сам проход указателями линеен (O(n)), но сортировка требует больше времени. Это решение не удовлетворяет строгому требованию O(n), но является классическим подходом к задаче.
• Пространственная сложность O(1) или O(log n): Если изменять исходный массив (arr.sort()), то дополнительная память почти не требуется (зависит от реализации sort). В примере мы создаем копию, что дает O(n), но это можно оптимизировать.
• Компромисс: Этот метод хорош, когда нельзя использовать дополнительную память (как в Решении #1), и допустима сложность O(n log n).