Two Sum II: Sorted Input
Дан массив целых чисел numbers, отсортированный в неубывающем порядке, и целое число target. Ровно одна пара разных позиций содержит два значения, сумма которых равна target. Верните эти две позиции в виде индексов с отсчётом от 0, сначала меньший индекс.
Функция
- numbersinteger-array
- отсортированный массив целых чисел
- targetinteger
- сумма двух значений, которой нужно достичь
- Возвращаетinteger-array
- два индекса с нумерацией от 0 [i, j], где i < j и numbers[i] + numbers[j] == target
Ограничения
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbersотсортирован по неубыванию.- Ровно одна пара индексов
i < jудовлетворяет условиюnumbers[i] + numbers[j] == target.
Примеры
- Ввод
- numbers = [-4, 1, 3, 8, 12]target = 9
- Вывод
- [1, 3]
- Пояснение
- 1 находится по индексу 1, а 8 — по индексу 3, и 1 + 8 = 9. Ни одна другая пара не дает в сумме 9: например, -4 + 12 = 8.
- Ввод
- numbers = [2, 2, 5, 7]target = 4
- Вывод
- [0, 1]
- Пояснение
- Две двойки с индексами 0 и 1 находятся на разных позициях, поэтому они могут образовать пару: 2 + 2 = 4.
- Ввод
- numbers = [-10, -3, 0, 6]target = -4
- Вывод
- [0, 3]
- Пояснение
- -10 с индексом 0 и 6 с индексом 3 дают -10 + 6 = -4. Ответ может охватывать весь массив.
+13 скрытых тестов при отправке
Дополнительный вопрос
Можешь решить эту задачу за время O(n) и с дополнительной памятью O(1)?
Подсказки
Открывайте по одной. Каждая подсказывает чуть больше.
Массив отсортирован. Посмотри на наименьшее и наибольшее значения вместе. О чём говорит их сумма, если она меньше
target?Если сумма первого значения и последнего значения слишком мала, то первое значение слишком мало для любого партнёра, потому что последнее значение уже является наибольшим. Его можно исключить.
Держите указатель у каждого конца. Если сумма слишком мала, переместите левый указатель вправо; если она слишком велика — переместите правый указатель влево. Остановитесь, когда сумма станет равна
target.
Решение
Хеш-таблица решает несортированный вариант за один проход, но требует O(n) памяти. Здесь массив отсортирован, и этот порядок подсказывает, в какую сторону двигаться. Поставь по одному указателю на каждом конце. Если сумма слишком мала, помочь может только большее значение слева; если она слишком велика — только меньшее значение справа. На каждом шаге одно значение исключается окончательно, поэтому за один проход можно найти пару без дополнительной памяти.
Проверьте каждую пару
Верно, но не успевает на самых больших тестах
Идея
Переберите все пары позиций i < j и проверьте, равна ли numbers[i] + numbers[j] значению target. Поскольку i движется слева направо, а j начинается сразу после него, у первой найденной пары меньший индекс уже будет первым.
Это верное решение, но оно не учитывает сортировку. При n = 10^4 имеется около 5 × 10^7 пар, а если ответ находится ближе к концу массива, вы проверите почти все из них. Для больших тестов это слишком медленно.
Алгоритм
- Выполни цикл по каждому индексу, используя
i. - Выполни цикл по
jотi+1до последнего индекса. - Если
numbers[i] + numbers[j]равноtarget, верни[i, j].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []Бинарный поиск для каждого партнёра
Идея
Когда ты фиксируешь первое значение numbers[i], его пару можно точно определить: target - numbers[i]. Часть массива справа от i отсортирована, поэтому бинарный поиск за O(log n) шагов может определить, есть ли там это значение.
Для [-4, 1, 3, 8, 12] и target = 9: при i = 0 парным значением было бы 13, но его нет. При i = 1 парное значение — 8, и поиск находит его по индексу 3. Ответ: [1, 3].
Поиск только справа от i позволяет сначала получить меньший индекс и не даёт значению образовать пару с самим собой. Пара уникальна, поэтому в этом диапазоне парное значение встречается не более одного раза, и любое совпадение будет ответом. Всего: n поисков по O(log n) каждый.
Алгоритм
- Перебирай
iот 0 доn-2. - Вычисли
need = target - numbers[i]. - Выполни бинарный поиск
needсреди индексов отi+1доn-1. - Если найдёшь его на позиции
mid, верни[i, mid].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []Два указателя с обоих концов
Идея
Начни с left = 0 и right = n-1 и посмотри на numbers[left] + numbers[right]. Если сумма равна target, задача решена. Если она слишком мала, numbers[left] не может входить в ответ: даже в паре с наибольшим из оставшихся значений эта сумма будет недостаточной. Поэтому передвинь left вправо. Если сумма слишком велика, numbers[right] тоже не может входить в пару, поскольку даже с наименьшим из оставшихся значений сумма превысит цель. Поэтому передвинь right влево.
При каждом перемещении отбрасывается одно значение, которое уже никогда не сможет входить в пару, а сама искомая пара не отбрасывается. Указатели встретятся не более чем через n-1 перемещений, поэтому просмотр занимает O(n) и использует две переменные.
Для [-4, 1, 3, 8, 12] при target = 9: -4 + 12 = 8 — слишком мало, поэтому left перемещается на индекс 1. Затем 1 + 12 = 13 — слишком много, поэтому right перемещается на индекс 3. Теперь 1 + 8 = 9, и ответ — [1, 3].
Алгоритм
- Установи
leftравным 0, аright—n-1. - Пока
left < right, вычисляйtotal = numbers[left] + numbers[right]. - Если
totalравенtarget, верни[left, right]. - Если
totalменьше, прибавь 1 кleft; если больше — вычти 1 изright.
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
Ловушки и крайние случаи
Цикл с двумя указателями короткий, поэтому ошибки скрываются в деталях вокруг него.
- Возврат позиций с нумерацией от 1. В этой версии нужны индексы с нумерацией от 0: для
[-4, 1, 3, 8, 12]иtarget = 9ответ —[1, 3], а не[2, 4]. В Lua и R перед возвратом вычтите 1. - Цикл с условием
left <= right. Когда указатели встречаются, для суммы одно значение будет использовано дважды. - Перемещение не того указателя. Если сумма слишком мала, нужно большее значение, а получить его можно только с помощью
left. - Отклонение повторяющихся значений. Для
[2, 2, 5, 7]приtarget = 4используются обе двойки, расположенные на разных позициях. - Переполнение. Ограничения здесь гарантируют, что каждая сумма помещается в 32-битное целое число. Если значения могут достигать
10^9, складывайте их, используя 64-битный тип.
Частые вопросы4
Почему для задачи Two Sum в отсортированном массиве работают два указателя?
Если сумма двух крайних значений слишком мала, левое значение слишком мало для любого ещё рассматриваемого партнёра, потому что правое крайнее значение — наибольшее из них. Его можно навсегда исключить. По той же логике правое значение исключают, когда сумма слишком велика. Искомая пара никогда не исключается, поэтому указатели остановятся на ней.
Какова временная сложность Two Sum II?
Решение с двумя указателями работает за время O(n) и использует O(1) дополнительной памяти: на каждом шаге один указатель сдвигается внутрь, и они встречаются не более чем через n-1 шагов. Бинарный поиск каждого соответствующего элемента занимает O(n log n), а проверка каждой пары — O(n²).
Почему бы не использовать хеш-таблицу, как в первом решении Two Sum?
Хеш-таблица тоже работает и выполняется за время O(n), но хранит до n значений. Благодаря сортировке эта память не нужна: двух указателей достаточно, чтобы определить, в какую сторону двигаться, исходя только из суммы. На собеседованиях задают эту версию задачи, чтобы проверить, используете ли вы заданный порядок.
Когда в данном случае лучше выбрать двоичный поиск?
Когда одно значение фиксировано и нужен только его партнёр. Если numbers[0] должно входить в пару, один бинарный поиск находит второй индекс за O(log n). Чтобы найти неизвестную пару, сканирование двумя указателями быстрее, чем n отдельных поисков.
Похожие задачи
Задачи на те же идеи. Решите две или три, и приём запомнится.
Python
def twoSumSorted(numbers, target):
# Напишите код здесьСлучай 1
Случай 2
Случай 3
Ввод
numbers = [-4, 1, 3, 8, 12] target = 9
Ожидается
[1, 3]