## Question

Given an array of integers, return indices of the two numbers such that they add up to a specific target. You may assume that each input would have exactly one solution, and you may not use the same element twice. Example: Given nums = [2, 7, 11, 15], target = 9, Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

## Explanation

### Naive solutions

First we come out with the simplest solution, iterate with array element, check whether there are two value’s sum is the target, if true, we get a result, so pseudo code is:

foreach(v1 in array) { foreach(v2 in array){ if (v2 == target - v1) { return (index v1, index v2) } }

Time complexity: \(O(N^2)\) Space complexity: \(O(1)\)

### Optimization with hashmap

Time general idea is using space to optimize time complexity. We can use a ** hashmap** to optimize the second loop from O(N) to O(1).

To build a hashmap, the key is the element of the array, and value is the index of the element. This hashmap can be constructed beforehand, but a better way is to construct in the same loop of checking.

Time complexity: \(O(N)\) Space complexity: \(O(N)\)

## C++

```
class Solution {
public:
vector<int> twoSum(vector<int>& arr, int target) {
map<int, int> m;
vector<int> result;
for (int i=0; i < arr.size(); i++) {
if ( m.find(target - arr[i]) == m.end() ) {
m[arr[i]] = i; // Note: key is element, value is index
}else{
result.push_back(m[target - arr[i]]);
result.push_back(i);
}
}
return result;
}
};
```

## Java

Java version is the same logic with Cpp version:

```
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
int complement = target - nums[i];
if (map.containsKey(complement)) {
return new int[] { map.get(complement), i };
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
```

## Python

Why we don’t need a hashmap in Python version, please note the second **if** test. It’s a pragmatic style for Python check whether a element is in array:

```
if elment in array:
....
```

Note we use ** nums[i+1:]** in checking, that means we use part of nums index begin with i+1. According to the document, the time complexity of ‘in’ operator is O(N) for list, so this implementation’s time complexity is: \(O(N^2)\)

```
class Solution(object):
def twoSum(self, nums, target):
for i in range(0, len(nums)-1):
if (target - nums[i]) in nums[i+1:]:
return [nums.index(nums[i]), nums.index((target-nums[i]), i+1)]
```

## Ruby

Ruby’s version is short, the logic is same with a Hashmap.

```
def two_sum(nums, target)
hash = {}
nums.each_with_index do |n, index|
first = hash[target - n]
if first != nil && first != index
return [first, index]
end
hash[n] = index
end
end
```