Сумма двух

Постановка задачи

nums = [2, 7, 11, 15], target = 9

[0, 1]

nums = [3, 2, 4], target = 6

[1, 2]

nums = [3, 3], target = 6

[0, 1]

Решение

Задача нахождения двух чисел в массиве с заданной суммой - это классика алгоритмического интервью на тему хеш-таблиц. Смысл в том, чтобы найти два числа в массиве, сумма которых равна заданному числу target.

Это своего рода "лакмусовая бумажка" для программиста. Интервьюер проверяет три вещи:

1. Знание структур данных: понимает ли кандидат, что такое хеш-таблица и как она ускоряет поиск.

2. Оптимизация: умеет ли программист уйти от "наивного" решения к оптимальному.

3. Базовая логика: насколько чисто кандидат пишет код и учитывает ли граничные случаи.

Можно быстро придумать простой подход перебором. Решение методом полного перебора пар для массива успешно проходит проверку на LeetCode:

function twoSum(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 [];
}

Здесь мы не используем никакие хитрые структуры данных, а просто перебираем все возможные комбинации пар чисел. Мы берем первое число и по очереди прибавляем к нему все остальные числа в массиве, проверяя, не получится ли в сумме target. Если не нашли - берем второе число и повторяем процесс, и так до конца.

Как мы уже знаем из разборов задач, такое решение методом полного перебора пар имеет сложность O(n²). Хотя оно и проходит тесты на LeetCode, на интервью такое решение сойдет только для уровня Junior или как стартовая точка для дальнейшей оптимизации. Интервьюер ждет алгоритм со сложностью менее O(n²).

В этой главе мы учимся работать с хеш-таблицами, поэтому решим эту задачу с использованием хеш-таблицы.

Идея решения:

Ключевое наблюдение заключается в том, что если у нас есть одно число из пары nums[i], то мы можем мгновенно узнать, какое число должно быть вторым в паре.

Так как nums[i] + nums[j] должно быть равно target, второе число в паре - это "дополнение", равное target - nums[i]. Мы могли бы искать "дополнение" линейным поиском, но это неэффективно. Тут нам нужен быстрый поиск. Какая структура данных используется для очень быстрого поиска? Мы уже знаем ответ: это хеш-таблица.

Подход с использованием хеш-таблицы, который проще всего понять, заключается в том, что мы добавляем в хеш-таблицу все числа. В качестве ключа используем само число, а в качестве значения - индекс числа в массиве. Далее проходим по массиву еще раз и для каждого числа nums[i] проверяем, есть ли в хеш-таблице для него "дополнение" target - nums[i]. Если есть и его индекс не равен i, то мы нашли нужную пару.

Этот подход можно еще улучшить, если делать все сразу за один проход по массиву. Мы будем добавлять числа в хеш-таблицу и в этой же итерации цикла сразу проверять, есть ли нужная пара для текущего числа. Однопроходное решение - это самый эффективный и элегантный способ. Мы ищем "дополнение" и заполняем таблицу одновременно.

Основные шаги:

1. Создаем хеш-таблицу. Тут будем хранить числа, которые мы уже видели. Ключ - само число, значение - его индекс: { значение: индекс }.

2. Идем циклом по массиву. На каждом шаге берем текущее число nums[i] и для него:

   • Находим "дополнение": diff = target - nums[i] и ищем его в таблице.
   • Если diff есть в таблице, то мы нашли пару. Текущий индекс - это i, а индекс второго числа берем из таблицы и возвращаем результат.
   • Если нет, добавляем текущее число и его индекс в таблицу: {nums[i], i}.

Рассмотрим это подробнее на примере:

nums = [2, 7, 11, 15]
target = 9

1. Создаем таблицу

• table = {} (пусто)
• target = 9

2. Идем циклом по массиву:

   2.1 Индекс i = 0, число nums[i] = 2. diff = 9 - 2 = 7. - Есть ли 7 в table? Нет. - Записываем текущее число в table = { 2: 0 }

2.2 Индекс i = 1, число nums[i] = 7. diff = 9 - 7 = 2. - Есть ли 2 в table? Да. - Мы нашли пару, индекс числа 2 из таблицы (это 0) и текущий индекс (1). - Возвращаем: [0, 1]

Оценка сложности

Временная сложность

Мы проходим по массиву всего один раз. Внутри цикла мы выполняем две основные операции: поиск в хеш-таблице и вставку в нее. В среднем поиск и вставка в хеш-таблицу занимают константное время O(1). Таким образом, n итераций * O(1) = O(n). Это значительно быстрее "наивного" решения с вложенными циклами за O(n²).

Пространственная сложность

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

Это классический пример компромисса: мы тратим больше памяти O(n) вместо O(1), чтобы получить выигрыш в скорости O(n) вместо O(n²).

Код решения

Приведем код решения.

func twoSum(nums []int, target int) []int {
    table := map[int]int{}
    for i := 0; i < len(nums); i++ {
        diff := target - nums[i]
        if j, ok := table[diff]; ok {
            return []int{j, i}
        }
        table[nums[i]] = i
    }
    return nil
}
 

Итоги

Задача учит эффективно использовать кэширование результатов и выбирать правильную структуру данных под конкретные ограничения.

1. Эффективный подход: использование хеш-таблицы в один проход.

2. Ключевая идея. Не искать второе число перебором, а вычислять "дополнение" diff и проверять, есть ли оно в хеш-таблице.

3. Главный компромисс. Мы жертвуем памятью (создаем таблицу), чтобы выиграть в скорости.

4. Альтернатива. Если массив уже отсортирован, лучше использовать метод двух указателей - это также быстро, но не требует лишней памяти.