Problem
Write a function that given an array of integer and a number k returns true if there is 2 numbers
which sum equals to k and false otherwise
Solution
1. Insert each elements into hash_set
2. If k - arr[i] in hash_set, return true
3. iterate to next elements
4. otherwise, return false
O(n) = n
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find the existence of 2 elements in array sum which equals to k
Created Date : 10-July-2013
Last Modified :
============================================================================
*/
#include <iostream>
#include <iomanip>
#include <hash_set>
#include <cassert>
using namespace std;
bool ExistSumEqualToK(int* arr, int len, int k)
{
assert(arr != NULL);
assert(len > 1);
hash_set<int> hs;
hs.insert(arr[0]);
for(int i = 1; i < len; ++i)
{
hs.insert(arr[i]);
if(hs.find(k - arr[i]) != hs.end()){
return true;
}
}
return false;
}
void DoTest(int* arr, int len, int target)
{
if(arr == NULL){
cout << "The array is null " << endl;
cout << "------------------------------" << endl;
return;
}
if(len < 1){
cout <<"The array is empty " << endl;
cout << "------------------------------" << endl;
return;
}
cout << "The array is " << endl;
for(int i = 0; i < len; ++i){
cout << setw(4) << arr[i];
}
cout << endl;
cout << "The target sum is " << target << endl;
if(ExistSumEqualToK(arr, len, target)){
cout << "Exists 2 elements which sum equals to " << target << endl;
}
else{
cout << "DO NOT exists 2 elements " << endl;
}
cout << "------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {1, 7, 3, 4, 5, 6, 2, 2, 4};
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 7);
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 0);
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 1);
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 3);
DoTest(arr, sizeof(arr)/sizeof(arr[0]), 9);
DoTest(arr, -1, 7);
DoTest(arr, 0, 7);
int* arr1 = NULL;
DoTest(arr1, 0, 7);
return 0;
}
Output
The array is
1 7 3 4 5 6 2 2 4
The target sum is 7
Exists 2 elements which sum equals to 7
------------------------------
The array is
1 7 3 4 5 6 2 2 4
The target sum is 0
DO NOT exists 2 elements
------------------------------
The array is
1 7 3 4 5 6 2 2 4
The target sum is 1
DO NOT exists 2 elements
------------------------------
The array is
1 7 3 4 5 6 2 2 4
The target sum is 3
Exists 2 elements which sum equals to 3
------------------------------
The array is
1 7 3 4 5 6 2 2 4
The target sum is 9
DO NOT exists 2 elements
------------------------------
The array is empty
------------------------------
The array is empty
------------------------------
The array is null
------------------------------
Press any key to continue . . .