# Two sum

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

### Solution

``````/**
* Two sum
* @param {number[]} nums
* @param {number} target
* @return {number[]}
* @time complexity: O(n^2)
* @space complexity: O(1)
*/
function twoSumNestedLoop(nums, target) {
for (let i = 0; i < nums.length; i++) {
for (let j = i + 1; j < nums.length; j++) {
if (nums[i] + nums[j] === target) {
return [i, j];
}
}
}
};
``````

``````
/**
* Two sum
* @param {number[]} nums
* @param {number} target
* @return {number[]}
* @time complexity: O(n)
* @space complexity: O(n)
*/
function twoSumOptimized(nums, target) {
const ans = {};

for (let i = 0; i < nums.length; i++) {
const val = target - nums[i];

if (ans[val] !== undefined) {
return [ans[val], i];
}

ans[nums[i]] = i;
}
};
```
```

### Test Case

``````describe('twoSum', () => {
describe('#twoSumOptimized', () => {
it('should return the correct indices', () => {
assert.deepEqual(twoSumOptimized([2, 7, 11, 15], 9), [0, 1]);
assert.deepEqual(twoSumOptimized([2, 7, 11, 15], 13), [0, 2]);
});
it('should return undefined', () => {
assert.deepEqual(twoSumOptimized([2, 7, 11, 15], 14), undefined);
});
});
describe('#twoSumNestedLoop', () => {
it('should return the correct indices', () => {
assert.deepEqual(twoSumNestedLoop([2, 7, 11, 15], 9), [0, 1]);
assert.deepEqual(twoSumNestedLoop([2, 7, 11, 15], 13), [0, 2]);
});
it('should return undefined', () => {
assert.deepEqual(twoSumNestedLoop([2, 7, 11, 15], 14), undefined);
});
});
});
``````
``````  Two Sum
#twoSumOptimized
✓ should return the correct indices
✓ should return undefined
#twoSumNestedLoop
✓ should return the correct indices
✓ should return undefined

4 passing (19ms)
``````

Mike Mai   Brooklyn, New York
I am full-stack web developer, passionate about building world class web applications. Knowledge in designing, coding, testing, and debugging. I love to solve problems.