Hash table solution to twoSum

Question

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:

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

Implement

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 []

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?

Answer 1

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 

Answer 2

You may assume that each input would have exactly one solution.

So there's no need to iterate over num twice. In fact, you won't even iterate over it for the full range, because you can return when you found the solution.

With the input given, I'd try this:

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

def twoSum(nums, target):
    for i in nums:
        for m in nums[nums.index(i)+1:]:
            if i + m == target:
                return [nums.index(i), nums.index(m)]

print(twoSum(nums, target))        

Say i + m is your target twoSum, you iterate over nums for each i and then look in the rest of num if there's any m for which i + m = target, and return when found.

Edit: This fails if you have duplicate integers in nums that add up to target, and it'll be slower if the solution is two elements near the end of nums.

Also: thank you for mentioning Leetcode, it's new to me. Nice!