round: 4
ticket_no: 02
source_no: 8
slug: two-sum
topic: Hash Table
difficulty: Easy
leetcode_id: 1
attempted: true
score: 2
verdict: partial
reviewed_at: 2026-09-15
---

# Билет 02 — Two Sum

## Условие (как предъявлено)

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

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

Constraints: `2 <= nums.length <= 10^4`; `-10^9 <= nums[i] <= 10^9`; `-10^9 <= target <= 10^9`.

## Ответ

> Дословно из `work-02-two-sum.md` (код как написан):

```ruby
def two_sum(nums, target)
  visited = {}

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

    if visited.key?(compliment)
      return [visited[compliment], i]
    end

    visited[num] = i unless visited.key?(num)
  end

  nil
end

# сложность O(n)
# mem: O(n/2) -> O(n)
```

> Проговаривание в чате (не в файле): «решение есть обязательно, поэтому внутри возврата что-то обязательно сработает… числа отрицательные тоже сработают».

## Разбор

**Что верно:**
- Идея хеша + проверка complement **до вставки** — канон, провал раунда 1 закрыт окончательно (R2: 2, идея верная, сложность не названа; сейчас код и сложность на месте).
- `unless visited.key?(num)` — не перезаписывает первое вхождение числа; безвредна, в рабочем пути даже не срабатывает (до вставки происходит return).
- Провал R1 `[3,3], target=6` → `[0,1]` — корректно.
- Прогон на Ruby: все примеры + отрицательные (`[-3,4]→[0,1]`, `[-1,-2,-3],-4→[0,2]`), дубликаты `[1,2,1],2→[0,2]`, крайние значения ±10^9 — всё OK.
- nil-заглушка недостижима: по условию решение гарантировано.

**Что упущено и ошибки:**
1. ❌ **Edge cases не написаны в файле** — проговаривание началось в чате, но в ответ не попало. Формат «ответ в файле» нарушен.
2. ⚠️ Из названного в чате: гарантия решения (верно), отрицательные числа (верно, но не доведено: по constraints ±10^9, в Ruby нет переполнения).
3. ❌ **Не назван главный edge case этой задачи — дубликаты значений** (`[3,3], target=6`): два разных индекса с одним значением. Именно его решение специально обрабатывает (проверка до вставки) — и именно его не проговорил. Первый fail R1 не отрефлексирован устно.
4. ⚠️ Порядок индексов: `return [visited[comp], i]` валиден, т.к. ответ «в любом порядке» и всегда `visited[comp] < i` — не проговорено.
5. ⚠️ `n >= 2` по constraints — пустой/одноэлементный массив невозможен, не проговорено.
6. ⚠️ **Память записана O(n/2) -> O(n)** — формально верно (константы отбрасываются), но `O(n/2)` выглядит небрежно; на интервью пиши просто O(n).

**Эталонная идея:**
Один проход с хешем «значение → индекс». Для каждого `nums[i]` ищем `target - nums[i]` в хеше: если есть — ответ `[hash[comp], i]`, если нет — записываем текущий элемент в хеш. Ключевой порядок: **сначала проверить, потом вставить** — иначе при дубликатах (`[3,3]`) вернём `[1,1]` (один индекс дважды) или затрём первое вхождение.

**Время:** O(n) — один проход, O(1) на операцию с хешем.

**Память:** O(n) дополнительная — хеш до n записей.

**Граничные случаи:** 1) дубликаты значений `[3,3], target=6` → `[0,1]` (разные индексы, одно значение; проверка до вставки); 2) отрицательные числа и отрицательный target `[-1,-2,-3], -4` → `[0,2]`; 3) `n >= 2` по constraints — пустой вход невозможен; 4) крайние значения ±10^9 — в Ruby переполнения нет, в C/Java проверить тип.

**Критерии:** идея ✅ · структура данных ✅ · сложность ✅ (названа, память с оговоркой O(n/2)) · граничные случаи ❌ (не в файле, в чате — частично, дубликаты пропущены)

**Канон сложности:** O(n) / O(n) — совпадает с `complexity-cheat-sheet.md`.

**Разбор задачи:** [`../../algo-solutions/01-must-have/05-hash-table/08-two-sum.md`](../../algo-solutions/01-must-have/05-hash-table/08-two-sum.md)