Two Sum

Problem

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.

Example

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

Return [1, 2]

Note

You may assume that each input would have exactly one solution

Challenge

Either of the following solutions are acceptable:

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

Solution

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.