Given an array of integers **input[]** and an integer **target**, the task is to return the index of two numbers such that they sum up to target.

**Input:** nums = [1, 4, 45, 6, 10, 8], target = 16

**Output:** [3,4]

**Input:** nums = [3,2,4], target = 6

**Output:** [1,2]

**Input:** nums = [3,4], target = 6

**Output:** [-1,-1]

## Solutions

### Method 1: In O(n) time and O(n) space

We can solve this problem in **O(n)** time and **O(n)** space.

The goal is to keep a **hash map** with the key representing **target-a[i]** and the value representing the **index**.

Iterate through the array from left to right; if **target-currentElement** is already in the map, return **[map.get(target-currentElement), i]**; otherwise, add the current element value and index to the map.

##### Complexity

The time complexity of this solution is **O(n)** and space complexity is **O(n)**.

### Method 2: In O (n log n) time and O(1) space

We can solve this problem in **O(n log n)** time and **O(1)** space.

The idea is to first **sort** the array and then use two pointers at both ends of the array. i.e. i=0, j= a.length-1.

If i+j < target, do i++, else if i+j > target, do j--, else return return [i, j].

##### Complexity

The time complexity of this solution is **O(n log n)** and space complexity is **O(1)**.

### Method 3: In O(n*n) time and O(1) space

We can solve this problem in **O(n ^{2})** time using two nested loops.

The idea is to check for every pair until the target is met; if no pair sums up to the target, return [-1, -1].

##### Complexity

The time complexity of this solution is **O(n*n)** and space complexity is** O(1)**.