Сложность: medium
Дан массив целых чисел numbers, индексированный с 1, который уже отсортирован в неубывающем порядке. Найдите два числа так, чтобы их сумма составляла заданное целевое число. Пусть эти два числа будут numbers[index1] и numbers[index2], где 1 <= index1 < index2 <= numbers.length.
Верните индексы этих двух чисел, index1 и index2, увеличенные на один, в виде массива из двух элементов [index1, index2].
Тесты генерируются таким образом, что существует ровно одно решение. Нельзя использовать один и тот же элемент дважды.
Ваше решение должно использовать только константное дополнительное пространство.
Пример:
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].
👨💻 Алгоритм:
1️⃣Инициализация указателей:
Используйте два указателя: один (left) начинается с начала массива, а другой (right) - с конца.
2️⃣Поиск решения:
Сравните сумму элементов, на которые указывают left и right, с целевым значением target.
Если сумма равна target, верните индексы этих элементов как решение.
Если сумма меньше target, увеличьте left (так как массив отсортирован и увеличение left увеличивает сумму).
Если сумма больше target, уменьшите right (чтобы уменьшить сумму).
3️⃣Продолжение до нахождения решения:
Перемещайте указатели left и right, повторяя сравнение, пока не будет найдено решение.
Учитывая, что задача гарантирует существование ровно одного решения, этот метод всегда найдет ответ.
😎 Решение:
class Solution:
def twoSum(self, numbers: List[int], target: int) -> List[int]:
low = 0
high = len(numbers) - 1
while low < high:
sum = numbers[low] + numbers[high]
if sum == target:
return [low + 1, high + 1]
elif sum < target:
low += 1
else:
high -= 1
return [-1, -1]
Ставь 👍 и забирай 📚 Базу знаний