Два указателя на отсортированном массиве: куда двигать при слишком маленькой сумме
Массив nums отсортирован по возрастанию. Ищем пару чисел с суммой target:
def two_sum_sorted(nums, target):
left, right = 0, len(nums) - 1
while left < right:
s = nums[left] + nums[right]
if s == target:
return (left, right)
# сюда нужно вписать движение указателей
return None
Текущая сумма s оказалась меньше target. Какое действие корректно?
- Сдвинуть `left` вправо: слева стоит наименьшее доступное число, увеличить сумму можно только заменой левого на большее
- Сдвинуть `right` влево: нужно уменьшить сумму, приблизив правый указатель к левому
- Сдвинуть оба указателя навстречу друг другу, чтобы гарантированно не пропустить ответ
- Сдвинуть `left` вправо и одновременно вернуть `right` в конец массива, чтобы перебрать все пары