Two Sum


Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are NOT zero-based.


Given numbers = [2, 7, 11, 15], target = 9

Return [1, 2]


You may assume that each input would have exactly one solution


Either of the following solutions are acceptable:

  • O(n) Space, O(nlogn) Time
  • O(n) Space, O(n) Time


To achieve O(n) time, we cannot use sort or nested loops. One solution is to store all the numbers in a hash map. (Why not hash set? we need to remember the position) This takes O(n). Then we loop through the array again and check if target - num[i] is already in the hash map, if so we have found a pair of numbers that sum up to target.

Online Judge