Two Sum

Question

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

Solution 1. Two for loop

def twoSum(nums, target):
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            if nums[i] + nums[j] == target:
                return [i, j]
                
twoSum([3,2, 1, 3, 6], 6)

## [0, 3]

This solution is easy to understand, but it’s not a efficient algorithm. The big $O$ notation is $O(n)=n^2$.

Why?

Because the total run times is $1+2+...+n=n\times (n+1)/2$.

Solution 2. Hash table

By using the idea of hash table, we can make look up time from $O(n)$ to $O(1)$.

def twoSum(nums, target):

  hash_table={}
  for i in range(len(nums)):    # make a hash table
    hash_table[nums[i]]=i
    
  for i in range(len(nums)):
    if target-nums[i] in hash_table: 
      if hash_table[target-nums[i]] != i:
            return [i, hash_table[target-nums[i]]]
  return []

input_list = [2,8,12,15]

twoSum(input_list, 20)

## [1, 2]

Looking up in a Hash table is $O(1)$. So we first build a hash table contain all the numbers. The total time si $O(n)$

Solution 3. enumerate

enumerate is a super useful build-in Python function. It allows us to loop over something and have an automatic counter. The results is equivalent to a hash table. But the code would be more concise.

It turns out we can do it in one-pass. While we iterate and inserting elements into the table, we also look back to check if current element’s complement already exists in the table. If it exists, we have found a solution and return immediately.

def twoSum(nums, target):
  hash_table = {}
  for i, num in enumerate(nums):
    if target-num in hash_table: 
      return([hash_table[target - num], i])
    hash_table[num] = i
  return []

input_list = [2,8,12,15]

twoSum(input_list, 20)

## [1, 2]

Summary

Familiar with hash table and enmerate will accelerate the algorithm.