---
title: Two Sum
difficulty: Easy
category: Hash Table
leetcode_id: 1
revision_count: 2
last_revision: 2026-09-12
---

# Two Sum

> **LeetCode:** [#1](https://leetcode.com/problems/two-sum/)
> **Сложность:** Easy
> **Категория:** Hash Table

## Условие

Дан массив целых чисел `nums` и целое `target`. Вернуть **индексы** двух чисел, которые в сумме дают `target`. Каждый вход имеет ровно одно решение, нельзя использовать один и тот же элемент дважды.

```
Input:  nums = [2, 7, 11, 15], target = 9  →  Output: [0, 1]
Input:  nums = [3, 2, 4],       target = 6  →  Output: [1, 2]
Input:  nums = [3, 3],          target = 6  →  Output: [0, 1]
```

## Ключевая идея

За один проход проверяем, встречался ли `complement` (разница между target и текущим числом) ранее — для этого храним `число → индекс` в хэш-таблице. Каждое число проверяем до того, как добавить его в таблицу (это гарантирует, что элемент не используется дважды).

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

- **Время:** O(n) — один проход по массиву
- **Память:** O(n) — хэш-таблица хранит до n элементов

## Решение (Ruby)

```ruby
# @param {Integer[]} nums
# @param {Integer} target
# @return {Integer[]}
def two_sum(nums, target)
  seen = {}

  nums.each_with_index do |num, i|
    complement = target - num

    return [seen[complement], i] if seen.key?(complement)

    seen[num] = i
  end
end
```

## Разбор на примере

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

seen = {}
i=0  num=2  complement=7  seen={}        →  not found, seen[2]=0
i=1  num=7  complement=2  seen={2→0}     →  found! return [0, 1]
```

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

seen = {}
i=0  num=3  complement=3  seen={}         →  not found, seen[3]=0
i=1  num=2  complement=4  seen={3→0}      →  not found, seen[2]=1
i=2  num=4  complement=2  seen={3→0, 2→1} →  found! return [1, 2]
```

## Edge Cases

- **Ровно одно решение всегда существует** (по условию задачи) — не нужно проверять `nil`.
- **Отрицательные числа**: `nums = [-3, 1, 0], target = -2` → complement = 1, находит [0, 1].
- **Дубликаты**: `nums = [3, 3], target = 6` — первый 3 кладётся в seen, второй находит complement=3 → [0, 1].

## Типичные ошибки

1. ❌ **Использовать один и тот же элемент дважды**: если проверять complement **после** добавления `seen[num] = i`, то для `nums = [3, 2, 4], target = 6` на i=0 найдём `seen[3]` = 0 и вернём [0, 0].
2. ❌ **Путаница индекс/значение**: в хэш кладём `num → index`, а ключ — это значение числа.

## Альтернативные подходы

| Подход | Время | Память | Комментарий |
|--------|-------|--------|-------------|
| Brute-force (два цикла) | O(n²) | O(1) | Проверяем все пары |
| **One-pass Hash Table** | **O(n)** | **O(n)** | **финальное решение** |

Brute-force — первый приходящий в голову вариант, но O(n²) не пройдёт на больших данных. Двухпроходный hash (сначала заполнить, потом проверять) тоже O(n), но хуже в один проход — не нужно отдельно обрабатывать случай дубликатов.

## Заметки после повторения

_— Заполняется после каждой тренировки._