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.

3

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.

6

7 // At each step we can do an O(1) lookup in the hash to see if target - num has

8 // already been added to the hash. If it has, we terminate processing and print

9 // the two numbers (along with their indices). Otherwise we add num to the hash

10 // and loop back to read the next input number.

11

12 // Overall performance is O(N) in the worst case, since in that case we must

13 // process each input item exactly once. (For each item, we perform one lookup

14 // into the hash, which adds only a small constant to the running time per

15 // iteration of the loop.)

16

17 // Usage: Pass the target value as a command line option, and the number array as

18 // values on stdin, one item per line.

19

20 #include <map>

21 #include <string>

22 #include <cstdlib>

23 #include <iostream>

24 #include <vector>

25

26 void two_sum( std::vector<long> vec, long target ) {

27 std::map<long, long> hash;

28

29 for ( long i=0; i < vec.size(); i++ ) {

30 hash[vec[i]] = i;

31 }

32

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).first != vec[i] ) ) {

40 std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << (*it).second << ")" << std::endl;

41 }

42 }

43 i++;

44 }

45 }

46

47 int main( int argc, char **argv ) {

48 char *endptr = NULL;

49 long target = strtol( argv[1], &endptr, 10);

50

51 std::vector<long> vec;

52 long num;

53 std::string s;

54

55 while ( std::cin >> s ) {

56 num = strtol( s.c_str(), &endptr, 10);

57 vec.push_back(num);

58 }

59

60 two_sum( vec, target );

61

62 exit(EXIT_SUCCESS);

63 }

64

65