重构二和问题的哈希表解决方案

Question

我尽最大努力解决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）使用哈希表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毫秒，比Python3在线提交的两个总和的46.66%快。内存使用率：16.1MB，不到Python3在线提交两次总和的5.08%。

我想重构代码，以便实现至少超过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]] = # ???