---
round: 3
ticket_no: 26
source_no: 8
slug: two-sum
topic: Hash Table
difficulty: Easy
leetcode_id: 1
attempted: true
score:
verdict:
reviewed_at:
---

# Билет 26 — Two Sum

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

Дан массив целых чисел `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]
```

Constraints: `2 <= nums.length <= 10^4`; `-10^9 <= nums[i] <= 10^9`; `-10^9 <= target <= 10^9`; существует ровно одно решение.

## Ответ

> Ну, мы, получается, проходим наш список и заполняем хэш. Значит, что у нас тут ключом будет являться ключом само число, а значение будет индекс, на котором мы его встретили. Дальше мы, когда переходим к следующему числу, мы проверяем, а есть ли в нашем хэше нужный нам комплемент, то есть дополняющий часть. Мы сравниваем его с целевым значением, что нам не хватает. Вот, и короче, смотрим. Ну, понятное дело, если число больше, то мы ничего не сравниваем. Хотя тут написано целые числа, то есть они в целом могут быть отрицательные, да, то есть это означает, что в целом там комплемент может быть. Все верно. Да, отрицательные тут допустимы. Так что вот такая идея. Вот. И как только мы встретили, мы, получается, в два индекса возвращаем: тот текущий и тот, который мы взяли из хэша. Ну и, соответственно, нужно контролировать, что мы не, знаете, само число с собой не пытались сравнить. Добавлять элемент в этот хэш после того, кк мы сдвинулись вправо.

## Разбор

**Что верно:**

**Что упущено и ошибки:**

**Эталонная идея:**

**Время:** O(...) — что доминирует

**Память:** O(...) дополнительная (+ O(...) на выход / стек рекурсии)

**Граничные случаи:** 1) ... 2) ... 3) ...

**Критерии:** идея ⚠️ · структура данных ⚠️ · сложность ⚠️ · граничные случаи ⚠️

**Канон сложности:** сверить с [`../complexity-cheat-sheet.md`](../complexity-cheat-sheet.md) (таблица по 32 задачам)

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