将哈希表解决方案重构为twoSum问题

Question

我尽力解决leetcode中的twoSum问题

给定一个整数数组，返回两个数字的索引，使它们相加到特定目标。

您可以假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。

例：

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）用哈希表O（1）搜索target - num [i]

实行

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毫秒，比两个Sum的Python3在线提交的46.66％快。内存使用：16.1 MB，不到5.03％的Python3在线提交的两个Sum。

我想重构代码，以便至少达到60％以上。

你能提供一些提示吗？

Answer 1

LeetCode问题的“解决方案”选项卡中的方法3似乎快于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]] = # ???