# 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`

.