# Two Sum Problem

### Question:

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

Each input would have exactly one solution.

``````Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums + nums = 2 + 7 = 9,
return [0, 1].
``````

### Think Out Loud:

Method 1: You can easily solve this problem by having two for loops. Get the first value from outer loop and the second value from the inner value and check the sum. But the time complexity of this method is O(n^2), which is too much for this problem.

Method 2: Generally speaking, to reduce the time complexity, you can add more space. One candidate is hash table. So let's have a hash table to the number as key and its index in the array as the value. And then, loop through the array, find the difference of target and current value. If the difference is in the hash table, then we find the answer. Wait! If the array is [3, 1, 5], the target is 6. Our algorithm will fail because the difference of 6 and 3 is 3, and 3 is in the hash table. What are we missing? We miss something in the condition, if the difference is in the hash table and the index of the difference in the hash table is not the index of current value, then we can claim we find the answer. Now, the time complexity is O(n) and space complexity is also O(n);

Method 3: What if you are not allowed to use hash table? Let's go back to Method 1. The gist of Method 1 is to use two pointers, the first pointer points to a value in the array, and the second pointer goes through the array from the beginning of the array to find the difference of target and the value pointed by the first pointer. The main issue is lots of numbers are scanned several times. Can we cut it down? Let's say if we know the sum of the value pointed by the first pointer and the value pointed by the second pointer is greater than the target, it will be great that the second pointer does not go forward. The answer is sort the array! Thus, the algorithm is to sort the array first, and have a left pointer pointing to the first value of the array and a right pointer pointing the last value of the array. If (the value pointed by the left pointer + the value pointed by the right pointer) is greater than the target, you will know you should move the right pointer to the left because anything in the right side of the right pointer is greater than the value pointed by the right pointer, which makes the sum bigger, and vice versa. The time complexity is O(nlog(n));

##### CPP Code (Method 2)
``````bool _is_in_map(unordered_map<int, int>& hash, int value) {
return hash.find(value) != hash.end();
}
vector<int> two_sum(vector<int> &numbers, int target) {
vector<int> result;
unordered_map<int, int> value_index_hash;

for(int i = 0; i < numbers.size(); i++) {
value_index_hash[numbers[i]] = i;
}

for(int i = 0; i < numbers.size(); i++) {
int difference = target - numbers[i];

if(_is_in_map(value_index_hash, difference) && i != value_index_hash[difference]) {
result.push_back(value_index_hash[difference]);
result.push_back(i);
break;
}
}
return result;
}
``````
##### Javascript Code (Method 2)
``````var twoSum = function(nums, target) {
const valueIndexHash = nums.reduce((previsouValue, currentValue, index) => {
previsouValue[currentValue] = index;
return previsouValue;
}, {});

var result = [];
nums.some((currentValue, index) => {
var difference = target - currentValue;
if(difference in valueIndexHash && valueIndexHash[difference] != index) {
result = [index, valueIndexHash[difference]];
return true;
}
});
return result;
};
``````
##### CPP Code (Method 3)
``````vector<int> two_sum(vector<int> &numbers, int target) {
vector<int> result;
vector<int> numbers_dup = vector<int>(numbers);

sort(numbers_dup.begin(), numbers_dup.end());

int left = 0, right = numbers_dup.size() - 1;
while(left <= right) {
int sum = numbers_dup[left] + numbers_dup[right];

if(sum == target) {
//find the idex of numbers_dup[left] and numbers_dup[right]
for(int i = 0; i < numbers.size(); i++) {
if(numbers[i] == numbers_dup[left] || numbers[i] == numbers_dup[right]) {
result.push_back(i);
}
if(result.size() == 2) {
return result;
}
}
}
else if(sum > target) {
right--;
}
else {
left++;
}
}
}
``````