Two Sum (Easy)

Бытовая аналогия

Представьте, что вы стоите у кассы и хотите расплатиться ровно двумя купюрами так, чтобы получилась нужная сумма — скажем, 9 рублей. Вы достаёте первую купюру (2 рубля) и думаете: «мне не хватает 7». Дальше вы не перебираете заново весь кошелёк — вы просто помните, что ищете семёрку. Как только семёрка попадётся, задача решена.

Именно так работает «умное» решение задачи Two Sum: вместо того чтобы каждый раз перебирать все купюры заново, мы запоминаем уже виденные числа и для каждого нового сразу проверяем — а не встречали ли мы уже его «недостающую половинку».

Условие

Дан списокИзменяемая упорядоченная коллекция элементов: [1, 2, 3]. По-английски list. чисел nums и число target. Нужно вернуть индексыНомер позиции элемента в последовательности. В Python нумерация с нуля: первый элемент — индекс 0. двух элементов, которые в сумме дают target. Гарантируется ровно одно решение.

Пример: nums = [2, 7, 11, 15], target = 9 → ответ [0, 1], потому что nums[0] + nums[1] = 2 + 7 = 9.

Наивное решение O(n²)

Перебрать все пары двумя циклами. Работает, но медленно — это как доставать из кошелька первую купюру и каждый раз заново перебирать все остальные:

Быстрое решение O(n) через словарь

Ключевая идея: для каждого числа x нам нужно target - x (дополнение). Будем запоминать виденные числа в словарьКоллекция пар «ключ → значение»: {"a": 1}. Быстрый доступ по ключу. По-английски dict. число → индекс и для каждого нового проверять, не встречали ли мы уже его дополнение.

Разбираем быстрый код по строкам

Этот код — образец, который стоит понять до последней буквы. Разберём каждую строкуТекстовое значение в кавычках: "привет". Неизменяема. По-английски string (str). циклаКонструкция, повторяющая блок кода: for перебирает элементы, while — пока условие истинно.:

• seen = {} — создаём пустой словарь. Здесь мы будем хранить пары «число → его индекс». Это наша «память» о том, что уже видели.
• for i, x in enumerate(nums) — идём по списку, получая сразу и индекс i, и значение x.
• need = target - x — вычисляем «недостающую половинку». Если сейчас x = 2, а target = 9, то need = 7.
• if need in seen — проверяем, не встречали ли мы уже это число раньше. Проверка «есть ли ключ в словаре» работает мгновенно — O(1).
• return [seen[need], i] — если встречали: возвращаем индекс той «половинки» (он лежит в словаре) и текущий индекс i.
• seen[x] = i — если не встречали: запоминаем текущее число и его индекс на будущее.

Ответ — [2, 3]. Числа 3 (индекс 2) и 8 (индекс 3) дают в сумме 11. Когда цикл доходит до x = 8, он ищет need = 11 - 8 = 3, а тройку мы уже видели и записали в seen с индексом 2. Поэтому ответ — [2, 3].

⚠️ Частые ошибки новичков

Очень распространённая ошибка — записывать число в словарь до проверки. Тогда для пары одинаковых чисел можно случайно «найти» само число дважды. Ниже код намеренно сломан: число добавляется в seen раньше проверки. Запустите, увидите неверный результат, и переставьте строки так, чтобы seen[x] = i шло после if.