Mercurial > algorithms
view two_sum/two_sum_hash.cpp @ 5:d48b3fb142f0
Updated comments. Correct subtle logic error in two_sum_hash.cpp that would have resulted in bad output when there are repeated values in the input.
| author | Eris Caffee <discordia@eldalin.com> |
|---|---|
| date | Mon, 04 May 2015 15:20:26 -0500 |
| parents | b06f215a4c69 |
| children |
line source
1 // Problem: given an input array of numbers, and a target value, find all pairs
2 // of numbers in the input which sum to the target value.
4 // Solution: Add the input numbers to a hash with the number as the hash key,
5 // and it's index position in the input as the hash value.
7 // For each value in the array, check to see if (target - value) is also in the
8 // hash and if so print the pair of nubmers. We need not consider values
9 // greater than target/2 since this would generate a duplicate pair when we
10 // eventually come across (target - value) itself in the array.
12 // We are using an extra O(N) amount of memory for the hash table, but doing so
13 // gives us O(1) lookup time to see if (target - value) is also in the array, so
14 // once the hash is built in O(N) time we need only another O(N) amount of time
15 // to find all pairs, yielding an overall O(N) running time.
17 // Usage: Pass the target value as a command line option, and the number array as
18 // values on stdin, one item per line.
20 #include <cstdlib>
21 #include <iostream>
22 #include <map>
23 #include <string>
24 #include <vector>
26 void two_sum( std::vector<long> vec, long target ) {
27 std::map<long, long> hash;
29 for ( long i=0; i < vec.size(); i++ ) {
30 hash[vec[i]] = i;
31 }
33 long lookfor;
34 long i = 0;
35 std::map<long, long>::iterator it;
36 while ( i < vec.size() ) {
37 if ( vec[i] <= target/2 ) {
38 lookfor = target - vec[i];
39 if ( ( ( it = hash.find(lookfor) ) != hash.end() ) && ( (*it).second != i ) ) {
40 std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << (*it).second << ")" << std::endl;
41 }
42 }
43 i++;
44 }
45 }
47 int main( int argc, char **argv ) {
48 char *endptr = NULL;
49 long target = strtol( argv[1], &endptr, 10);
51 std::vector<long> vec;
52 long num;
53 std::string s;
55 while ( std::cin >> s ) {
56 num = strtol( s.c_str(), &endptr, 10);
57 vec.push_back(num);
58 }
60 two_sum( vec, target );
62 exit(EXIT_SUCCESS);
63 }