Problems

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