two sum метод двух указателей
Решаю задачку две суммы с литкода: https://leetcode.com/problems/two-sum/ (найти пару целых чисел в массиве которая в сумме равна заданному числу; вывести индексы этих пар) На [3, 2, 4] валиться если решаю так:
nums.sort()
left, right = 0, len(nums) - 1
while left < right:
summa = nums[left] + nums[right]
if summa == target:
return left, right
elif target > summa:
left += 1
elif target < summa:
right -= 1
Понятно почему - мы переставили индексы. Но во всех других случаях работает. Везде говорится, что методом двух указателей эта задача 100% решается. Как решить именно этим методом и почему так
Ответы (1 шт):
Метод двух указателей работает для сортированного массива. Собственно, nums.sort() вы для этого и используете, но индексы не сохраняете.
Используйте два цикла (медленно), хэш-таблицу (быстро, но память требуется, при размере задачи 10^4 это не проблема), или, если требуется именно метод двух указателей - сортируйте вместе с индексами (параллельный массив или сделать список пар значение-индекс (кортежей или списков))
ns = [(v, i) for i, v in enumerate(nums)]
ns.sort()
left, right = 0, len(ns) - 1
while left < right:
summa = ns[left][0] + ns[right][0]
if summa == target:
return ns[left][1], ns[right][1]
elif target > summa:
left += 1
elif target < summa:
right -= 1