Two sum problem

Problem

Given N digits, find two numbers whose sum is equal to the given number T.

Answer

Using the hashtable, we can easily check if any two numbers are equal to T.

Here is algorithm.

1. Put all numbers into a hashtable, $O(N)$

2. Iterate over the N digits assuming there are in a list.

3. For each number, n, check if T-n exists in the hashtable.


Running time $O(N)$ for hashtable, $O(N log N)$ for map.


The following is the code.

	#include <map>
	#include <iostream>
	using namespace std;
	class TwoSum {
	public:
	void store(int input)
	{
	if (hashtable.find(input) == hashtable.end())
	{
	hashtable[input] = input;
	}
	}
	bool test(int val)
	{
	map<int, int>::iterator iter;
	for (iter = hashtable.begin(); iter != hashtable.end(); iter++)
	{
	int cur = iter->second;
	int left = val - cur;
	if (hashtable.find(left) != hashtable.end())
	return true;
	}
	return false;
	}
	private:
	map<int, int> hashtable;
	};
	int main ()
	{
	TwoSum t;
	t.store(1);
	t.store(-2);
	t.store(3);
	t.store(6);
	cout << " sum 4 = "<<t.test(4)<<endl;
	cout << " sum -1 = "<<t.test(-1)<<endl;
	cout << " sum 9 = "<<t.test(9)<<endl;
	cout << " sum 10 = "<<t.test(10)<<endl;
	cout << " sum 5 = "<<t.test(5)<<endl;
	cout << " sum 0 = "<<t.test(0)<<endl;
	return 1;
	}

view raw twosum_v1.cpp hosted with ❤ by GitHub

I will post another code implementation if I find better implementation.