The Two Sum Algorithm using HashMap in C++/Java

Given an array of integers nums and an integer target, return indices of the two numbers such that they add up to target. You may assume that each input would have exactly one solution, and you may not use the same element twice. You can return the answer in any order.

Example 1:
Input: nums = [2,7,11,15], target = 9
Output: [0,1]
Output: Because nums[0] + nums[1] == 9, we return [0, 1].

Example 2:
Input: nums = [3,2,4], target = 6
Output: [1,2]

Example 3:
Input: nums = [3,3], target = 6
Output: [0,1]

Two Sum Algorithm using Hash Table

Using Hashmap is very common in accelerating solutions and reducing algorithm complexity. A Hashmap is a data structure that is aimed for high performance lookup, indexing items etc.

In C++, you can use std::map<type, type> to create a hash map, also known as associate array that maps a key to a value (keypair). In Java, this is similar via java.util.Hashtable

We use hash map to make solutions faster.

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        int len = numbers.size();
        vector r;
        for (int i = 0; i < len - 1; i ++) {
            int k = target - numbers[i];
            for (int j = i + 1; j < len; j ++) {
                if (numbers[j] == k) {
                    r.push_back(i + 1);
                    r.push_back(j + 1);
                    return r;
                }
            }
        }
        return r;
    }
};

However, the same solution, rewritten in Java gets accepted in 684ms. (why?)

public class Solution {
    public int[] twoSum(int[] numbers, int target) {
        // Note: The Solution object is instantiated only once and is reused by each test case.
        int len = numbers.length;
        for (int i = 0; i < len - 1; i ++) {
            int k = target - numbers[i];
            for (int j = i + 1; j < len; j ++) {
                if (numbers[j] == k) {
                    return new int[]{i + 1, j + 1};
                }
            }
        }
        return null;
    }
}

With Hashmap, we can reduce the running time to O(n) (and O(n) space). In C++, the following code is accepted in 60ms.

#include <map>

using namespace std;

class Solution {
public:
    vector twoSum(vector &numbers, int target) {
        int len = numbers.size();
        map<int, int> r;
        vector rr;
        for (int i = 0; i < len; i ++) {
            if (r.find(numbers[i]) == r.end()) { // if not exist
                r[numbers[i]] = i;  // add it to the map
            }
            int j, num = target - numbers[i];
            if ((r.find(num) != r.end()) && ((j = r[num]) < i)) {
                rr.push_back(j + 1);
                rr.push_back(i + 1);
                return rr;
            }
        }
        return rr;
    }
};

It is O(n). For each number, we add it to the hash map if not exist. The keypair stores the value and its index in the array. And we check another number for existence. If yes, we have a solution, and output the corresponding indices.

To check if a key exists in the map, we use map::find(key) != map::end(). The same technique can be used in Java.

import java.util.Hashtable; //import hashtable utility
public class Solution {
    public int[] twoSum(int[] numbers, int target)
    {
        int []a = new int[2];
        Hashtable<Integer, Integer> nums = new Hashtable<Integer, Integer>();
        for (int i=0; i<numbers.length; i++)
        {
            //put number into hash table (if it's not already there)
            Integer n = nums.get(numbers[i]);
            if (n==null) nums.put(numbers[i], i); //subtract array element from target number
            n = nums.get(target-numbers[i]); 
            if (n!=null && n<i)
            {//if such number exists in the table return the indices.
                a[0]=n+1;
                a[1]=i+1;
                return a;
            }
        }
     return a;
    }
}

This puzzle is quite similar to C++ Algorithms to Find Pair of Sum Given a Collection of Numbers

See also: Teaching Kids Programming – Two Sum Algorithm

Two Sum Variation Problems

• Teaching Kids Programming - Two Sum in Binary Search Tree via Inorder and Two Pointer Algorithm
• Teaching Kids Programming - Count Pairs Whose Sum is Less than Target (Two Pointer Algorithm)
• Teaching Kids Programming - Sum of Two Numbers Less Than Target using Two Pointer Algorithm
• Teaching Kids Programming - Two Pointer Algorithm to Solve Four Sum Problem
• Teaching Kids Programming - Recursive Algorithm to Find the Sum of Two Numbers in BSTs
• Two Pointer Algorithm to Count the Sum of Three Numbers Less than Target
• Recursive and Two Pointer Algorithms to Determine Four Sum
• Algorithms to Check Sum of Two Numbers in Binary Search Trees
• Teaching Kids Programming - 3 Different Approaches to Solve Two-Sum Problem
• How to Design a Two-Sum Data Structure?
• How to Find the Closest Sum of Three in an Array using Two Pointer Algorithm? (3Sum Closest)
• Teaching Kids Programming - Three Sum Algorithm
• Teaching Kids Programming – Two Sum Algorithm when Input Array is Sorted
• Teaching Kids Programming – Two Sum Algorithm
• Two Pointer Algorithm to Find Maximum Two Sum Less Than K
• The Two Sum Algorithm using HashMap in C++/Java

–EOF (The Ultimate Computing & Technology Blog) —