Task:
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.

Examples :

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

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

This problem was taken from Leetcode

One pass hash table.

Let’s take this example: nums = [2, 7, 11, 15], target = 9
The brute force solution might be to loop through each value in the nums array, and to add with each other value in the array and to compare with the target result.

Optimize the algorithm using hash table

The idea is to store the array into a hash table where keys will be the values of the array (i.e: 2, 7, 11, 15) and the values: the element index (i.e: 0,1,2,3)
key:value
2 : 0,
7 : 1,
11:2,
15:3

This way all we need to do is:
– Iterate through the array once.
– For each value calculate what number could add to the target value ( x = target – nums[i])
– Dynamically add the next key-value pair into the hashmap

The solution:

Java Script

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    var hashMap = {};


    for(var i in nums) {                
            
        var test = target - nums[i];
        if(hashMap[test]) {
            return [parseInt(hashMap[test]), parseInt(i)];
        }     
        var key = nums[i];
        hashMap[key] = i;   
    }
};

C++

class Solution {
    
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        
        vector<int> result;

        std::map<int, int> buffer;
        for(int i = 0;i < nums.size(); i++) {
            int key = nums[i];
            int test = target - nums[i];

            if(buffer[test] != 0) {
                result = {buffer[test] -1, i};
                break;
            }
            buffer[key] = i + 1;
        }
        return result;
    }
};