Two Sum

Лёгкая№1найти пару

Дан массив чисел и сумма. Нужно найти два разных элемента, которые дают эту сумму, и вернуть их индексы. Такая пара ровно одна. Наш пример: [5, 1, 8, 6, 5, 3] и сумма 10 — ответ [0, 4], две пятёрки.

1 Two SumРазбор · 1×

Пример: [5, 1, 8, 6, 5, 3], сумма 10. Под массивом — словарь: число и индекс, на котором оно стоит.

051128364553seenчисло: индекс—
ещё не дошлив словаретекущее числоего параответ

Начинаем с пустого словаря: ещё ни одного числа не видели

01/21
сначала · назад · пуск · шаг
Скорость
1function twoSum(nums, target):
2 seen = empty map
3 for i from 0 to len(nums) - 1:
4 need = target - nums[i]
5 if need in seen:
6 return [seen[need], i]
7 seen[nums[i]] = i
состояние
seen
{}
i
–
need
–
историянажмите шаг, чтобы вернуться

← → шаг · пробел — пауза

Почему это работает

  1. Каждое число заранее знает свою пару: сумма минус само число. Вопрос только в том, встречали ли мы её раньше, и словарь отвечает на него сразу.
  2. Сначала ищем, потом записываем. Иначе первая 5 нашла бы в словаре саму себя и вернула [0, 0].
  3. Если пара стоит на j < i, то когда мы дойдём до i, число с индекса j уже будет в словаре. Значит, пару не пропустим, и хватает одного прохода.

Сложность

Время O(n): один проход, а поиск и запись в словаре в среднем O(1). Память O(n): в словаре могут оказаться все числа.

дальшеТеперь реши её сам, без подсказок.

Решить на LeetCode ↗

Задача и её условие принадлежат LeetCode. Здесь — наш пересказ, наш пример и наше решение. Patterns Hero не связан с LeetCode.