Блог

Я больше всего стараюсь решить проблему с двумя суммами в leetcode

Учитывая массив целых чисел, верните индексы двух чисел таким образом, чтобы они в сумме соответствовали определенной цели.

Можно предположить, что каждый ввод будет иметь ровно одно решение, и вы не можете использовать один и тот же элемент дважды.

Пример:

 Given nums = [2, 7, 11, 15], target = 9,

Because nums[0]   nums[1] = 2   7 = 9,
return [0, 1].
  

План:

1) перебор для повторения len (nums) O (n)
2) поиск целевого числа[i] с помощью хэш-таблицы O (1)

Реализовать

 class Solution:
    def twoSum(self, nums: List[int], target: int) -> List[int]:
        nums_d = {}
        for i in range(len(nums)):
            nums_d.setdefault(nums[i], []).append(i)

        for i in range(len(nums)):
            sub_target = target - nums[i]
            nums_d[nums[i]].pop(0) #remove the fixer
            result = nums_d.get(sub_target)#hash table to search 

            if result: 
                return [i, result[0]]
        return []
  

Я потратил часы на это решение, но обнаружил, что ответ принят, но не набрал 60 баллов.

Время выполнения: 60 мс, быстрее, чем 46,66% онлайн-заявок на Python3 для Two Sum. Использование памяти: 16,1 МБ, менее 5,08% онлайн-заявок на Python3 для Two Sum.

Я хочу реорганизовать коды так, чтобы достичь по крайней мере скорости, превышающей 60%.

Не могли бы вы, пожалуйста, дать подсказки?

Похоже, что подход 3 на вкладке «Решение» в задаче на LeetCode выполняется быстрее, чем на 80%. Вот неполный код, который вам нужно заполнить:

 def twoSum(self, nums: List[int], target: int) -> List[int]:
  map = # ???
  for i in range(len(nums)):
    complement = # ???
    if complement in map:
      return # ???
    map[nums[i]] = # ???