MiddleКодОчень частоЕщё не отвечали
Two Sum: индексы двух чисел с суммой, равной цели
Верните индексы двух чисел, дающих в сумме target.
Требования:
- Считайте, что ровно одна верная пара есть; верните её два индекса.
- Нельзя использовать один и тот же элемент дважды.
- Цель — O(n) время, а не перебор за O(n²).
def two_sum(nums, target):
# ваш код здесьДопишите реализацию.
Используйте словарь «значение → индекс»: для каждого n, если target - n уже встречалось, верните оба индекса; иначе сохраните n -> i. Один проход, O(n) время и O(n) память — против перебора двойным циклом за O(n²). enumerate удобно даёт индекс.
- ✗Возвращать значения, а не их индексы
- ✗Использовать один и тот же элемент дважды для пары
- ✗Соглашаться на двойной цикл за O(n²), когда ожидается O(n)
- →Как изменить решение, если список уже отсортирован?
- →Что меняется, если верных пар может быть несколько или ни одной?
Оглавление
Задача
Реализуйте two_sum: верните индексы двух чисел списка, дающих в сумме target, за один проход.
Решение
def two_sum(nums, target):
seen = {} # значение -> индекс
for i, n in enumerate(nums):
if target - n in seen:
return [seen[target - n], i]
seen[n] = i
return []Ключевые моменты
- Один проход: дополнение
target - nищется в словаре за O(1), поэтому суммарно O(n). - Сохраняем
nпосле проверки — иначе элемент мог бы составить пару сам с собой. - Перебор двойным циклом тоже верен, но это O(n²); словарь меняет память на скорость.
Оглавление
