1

我尽量解决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) 使用哈希表搜索目标 - num[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 毫秒，比 Python3 在线提交的 46.66% 的两和要快。内存使用：16.1 MB，不到 Python3 在线提交的 Two Sum 的 5.08%。

我想重构代码，以便至少快于 60%。

你能提供提示吗？

4

1 回答 1

0

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]] = # ???
于 2019-03-22T10:46:53.497 回答