Two Sum II - Input Array Is Sorted

Средняя№167навстречу

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

167 Two Sum II - Input Array Is SortedРазбор · 1×

Пример: [1, 4, 6, 7, 10, 13], сумма 16. Указатели стоят на концах: мало — левый идёт вправо, много — правый идёт влево.

01142637410513left
ещё возможныпроверяемая параотброшенынайденная пара

left — на самом маленьком числе, 1

01/21
сначала · назад · пуск · шаг
Скорость
1function twoSumSorted(numbers, target):
2 left = 0
3 right = len(numbers) - 1
4 while left < right:
5 sum = numbers[left] + numbers[right]
6 if sum < target:
7 left = left + 1
8 else if sum > target:
9 right = right - 1
10 else:
11 return [left + 1, right + 1]
состояние
left
0
right
–
sum
–
историянажмите шаг, чтобы вернуться

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

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

  1. Числа отсортированы, поэтому сдвиг левого вправо может сумму только увеличить, а сдвиг правого влево — только уменьшить.
  2. Сдвиг отбрасывает число навсегда. Если суммы мало, левое число с любым другим из оставшихся даст не больше, значит, пары у него нет. Много — то же для правого.
  3. В отличие от карточки, ответ — номера с 1, а не индексы: к каждому указателю прибавляем 1.

Сложность

Время O(n): каждый шаг сдвигает один указатель внутрь, так что шагов не больше n − 1. Память O(1): только два указателя и сумма.

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

Решить на LeetCode ↗

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