Hash table solution to twoSum I try the most to solve a twoSum problem in leetcode 


  Given an array of integers, return indices of the two numbers such that they add up to a specific target.
  
  You may assume that each input would have exactly one solution, and you may not use the same element twice.
  
  Example:
  
  Given nums = [2, 7, 11, 15], target = 9,
  
  Because nums[0] + nums[1] = 2 + 7 = 9,
  return [0, 1].


The plan:


brute force to iterate len(nums)   O(n)   
search for target - num[i] with a hash table   O(1)


Implement

class Solution:
    def twoSum(self, nums: List[int], target: int) -&gt; 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 []


I strives  hours for this solution but found that answer accepted but not passed Score 60.


  Runtime: 60 ms, faster than 46.66% of Python3 online submissions for Two Sum.
  Memory Usage: 16.1 MB, less than 5.08% of Python3 online submissions for Two Sum.


I want to refactor the codes  so that to achieve at least faster than 60%.

Could you please provide hints?
First some stylistic points


nums_d.setdefault(nums[i], []).append(i)

The setdefault is unnecessary here, you can assign a list normally

nums_d[nums[i]] = [i]

When you need both the index and the element use enumerate see PEP279


nums_d = {}
for i in range(len(nums)):
    nums_d.setdefault(nums[i], []).append(i)



nums_d = {}
for i, e  in enumerate(nums):
    nums_d[e] = [i]

Use comprehension when possible (They use the C style looping and is considered to be faster)

nums_d = { e: [i] for i, e  in enumerate(nums) }



Hint

You loop over nums twice, but this can be done in one loop! To make it O(n)

Whenever you visit a new element in nums ->

Check if it's sum complement is in nums_d, else add the target - element to the dictionary with the index as value t - e : i


   nums_d = {}
for i, e in enumerate(nums):
    if e in nums_d:
        return [nums_d[e], i]
    nums_d[target - e] = i