1. Two Sum

Задача

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

Примеры

Пример 1

Input: nums = [2,7,11,15], target = 9
Output: [0,1]

Пояснение

nums[0] + nums[1] == 9, поэтому возвращаем [0, 1].

Пример 2

Input: nums = [3,2,4], target = 6
Output: [1,2]

Пример 3

Input: nums = [3,3], target = 6
Output: [0,1]

Решение

Решение

/**
 * Временная сложность: O(n) - один проход по массиву
 * Пространственная сложность: O(n) - HashMap может хранить до n элементов
 * 
 * @param {number[]} nums - массив целых чисел
 * @param {number} target - целевая сумма
 * @return {number[]} - массив из двух индексов
 */
function twoSum(nums, target) {
    // Создаем Map для хранения пар: число -> индекс
    const map = new Map();
 
    // Проходим по массиву один раз
    for (let i = 0; i < nums.length; i++) {
        // Вычисляем комплемент (дополнение до target)
        const complement = target - nums[i];
 
        // Проверяем, встречали ли мы это число ранее
        // Поиск в Map выполняется за O(1)
        if (map.has(complement)) {
            // Нашли пару! Возвращаем индексы
            return [map.get(complement), i];
        }
 
        // Сохраняем текущее число и его индекс
        // Вставка в Map выполняется за O(1)
        map.set(nums[i], i);
    }
 
    // Если решение не найдено (по условию задачи это не должно произойти)
    return [];
}
 
// Тестирование примеров
console.log(twoSum([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSum([3, 2, 4], 6)); // [1, 2]
console.log(twoSum([3, 3], 6)); // [0, 1]

Решение 2 (Object)

  /**
   * Временная сложность: O(n)
   * Пространственная сложность: O(n)
   */
  function twoSumObject(nums, target) {
      const seen = {};
 
      for (let i = 0; i < nums.length; i++) {
          const complement = target - nums[i];
 
          if (complement in seen) {
              return [seen[complement], i];
          }
 
          seen[nums[i]] = i;
      }
 
      return [];
  }

Решение 3 (Two Pointers)

/**
 * Временная сложность: O(n log n) - из-за сортировки
 * Пространственная сложность: O(n) - для хранения пар [значение, индекс]
 */
function twoSumTwoPointers(nums, target) {
    // Создаем массив пар [значение, оригинальный индекс]
    // Это нужно, чтобы не потерять оригинальные индексы после сортировки
    const numsWithIndex = nums.map((num, index) => [num, index]);
 
    // Сортируем по значению
    // O(n log n) - временная сложность сортировки
    numsWithIndex.sort((a, b) => a[0] - b[0]);
 
    let left = 0;
    let right = numsWithIndex.length - 1;
 
    // Двигаем указатели навстречу друг другу
    // O(n) - временная сложность прохода
    while (left < right) {
        const sum = numsWithIndex[left][0] + numsWithIndex[right][0];
 
        if (sum === target) {
            // Возвращаем оригинальные индексы
            return [numsWithIndex[left][1], numsWithIndex[right][1]];
        } else if (sum < target) {
            // Нужна большая сумма - двигаем левый указатель вправо
            left++;
        } else {
            // Нужна меньшая сумма - двигаем правый указатель влево
            right--;
        }
    }
 
    return [];
}
 
// Тест
console.log(twoSumTwoPointers([2, 7, 11, 15], 9)); // [0, 1]
console.log(twoSumTwoPointers([3, 2, 4], 6)); // [1, 2]

Решение 4 (Brute Force)

/**
 * Временная сложность: O(n²)
 * Пространственная сложность: O(1)
 */
function twoSumBruteForce(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];
            }
        }
    }
    return [];
}