Оптимизация задачи Two sum с Leetcode

Question

Есть задача c LeetCode. Условие состоит в том, что дан список int-ов nums и int target и нужно вернуть индексы двух чисел, которые в сумме составляют target. Я написал следующий алгоритм для решения задачи:

def twoSum(self, nums: List[int], target: int) -> List[int]:
    if all(i <= 0 for i in nums): 
        nums = [abs(i) for i in nums]
        target = abs(target)
    for i in range(min(nums) - 1, target + 1):
        j = target - i
        if i != j:
            if i in nums and j in nums:
                return [nums.index(i), nums.index(j)]
        else:
            if nums.count(i) > 1:
                return [n for n, m in enumerate(nums) if m == i][:2]

Он проходит основные тесты, но тесты с большими числами проваливает — не хватает времени. Как его можно оптимизировать?

Answer 1

Используйте словарь - кладите в него пары элемент:индекс. Если в словаре уже есть ключ, который образует нужную сумму c текущим элементом - нашли.

dct = dict()
for i, x in enumerate(nums):
    if target - x in dct:
        return [i, dct[target - x]]
    else:
        dct[x] = i

Другой вариант - отсортировать список пар [элемент,индекс] и идти с двух концов

БЛОГ НА HUSL

Оптимизация задачи Two sum с Leetcode

Ответы (1 шт):