MaiDeveloper

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];
      }
    }
  }
};

Advanced Solution


/**
 * 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
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.