Post date: Jul 13, 2013 6:15:36 AM
Question
Design an algorithm to find all pairs of integers within an array which sum to a specified value.
Solution
/*
============================================================================
Author : James Chen
Email : a.james.chen@gmail.com
Description : Find all pair of number in array which sum to a specified value
Created Date : 13-July-2013
Last Modified :
============================================================================
*/
#include <unordered_map>
#include <iostream>
#include <iomanip>
using namespace std;
using namespace stdext;
static void PrintPairsSumTo(int* arr, int len, int sum)
{
unordered_map<int, int> hs;
for(int i = 0; i < len; ++i)
{
if(hs.find(sum - arr[i]) != hs.end()){
hs[sum - arr[i]] ++;
}
else if(arr[i] == sum - arr[i] && (hs.find(arr[i]) != hs.end())){
hs[arr[i]] ++;
}
if(hs.find(arr[i]) == hs.end() && hs.find(sum - arr[i]) == hs.end())
{
hs[arr[i]] = 0;
}
}
for(auto it = hs.begin(); it != hs.end(); ++it)
{
if (it->second != 0)
{
cout << setw(3) << it->first;
cout << " + " << setw(3) << sum - it->first;
cout << " = " << setw(3) << sum << endl;
}
}
}
static void DoTest(int* arr, int len, int sum)
{
cout << "The array is " << endl;
for(int i = 0; i < len; ++i)
{
cout << setw(3) << arr[i];
}
cout << endl;
cout << "Find two elements that sum to " << sum << endl;
PrintPairsSumTo(arr, len, sum);
cout << "------------------------------------" << endl;
}
int main(int argc, char* argv[])
{
int arr[] = {1};
DoTest(arr, sizeof(arr)/ sizeof(arr[0]), 0);
DoTest(arr, sizeof(arr)/ sizeof(arr[0]), 1);
int arr1[] = { 1, 1, 1, 2, 0, 2, 2, 3, 4, 5, 5, -1, -2, -3 };
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]), -4);
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]), -3);
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]), -2);
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]), -1);
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]), 0);
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]), 3);
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]), 4);
DoTest(arr1, sizeof(arr1)/ sizeof(arr1[0]), 10);
return 0;
}
Output
The array is
1
Find two elements that sum to 0
------------------------------------
The array is
1
Find two elements that sum to 1
------------------------------------
The array is
1 1 1 2 0 2 2 3 4 5 5 -1 -2 -3
Find two elements that sum to -4
-1 + -3 = -4
------------------------------------
The array is
1 1 1 2 0 2 2 3 4 5 5 -1 -2 -3
Find two elements that sum to -3
0 + -3 = -3
-1 + -2 = -3
------------------------------------
The array is
1 1 1 2 0 2 2 3 4 5 5 -1 -2 -3
Find two elements that sum to -2
1 + -3 = -2
0 + -2 = -2
------------------------------------
The array is
1 1 1 2 0 2 2 3 4 5 5 -1 -2 -3
Find two elements that sum to -1
1 + -2 = -1
2 + -3 = -1
0 + -1 = -1
------------------------------------
The array is
1 1 1 2 0 2 2 3 4 5 5 -1 -2 -3
Find two elements that sum to 0
1 + -1 = 0
2 + -2 = 0
3 + -3 = 0
------------------------------------
The array is
1 1 1 2 0 2 2 3 4 5 5 -1 -2 -3
Find two elements that sum to 3
1 + 2 = 3
0 + 3 = 3
4 + -1 = 3
5 + -2 = 3
------------------------------------
The array is
1 1 1 2 0 2 2 3 4 5 5 -1 -2 -3
Find two elements that sum to 4
1 + 3 = 4
2 + 2 = 4
0 + 4 = 4
5 + -1 = 4
------------------------------------
The array is
1 1 1 2 0 2 2 3 4 5 5 -1 -2 -3
Find two elements that sum to 10
5 + 5 = 10
------------------------------------
Press any key to continue . . .