1 // Problem: given an input array of numbers, and a target value, find two numbers

2 // in the input which sum to the target value. Do so with worst case performance

3 // of O(N).

4

5 // Solution: add the input numbers to a hash as they are read, with the number

6 // as the hash key, and it's index position in the input as the hash value.

7

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

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

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

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

12

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

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

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

16 // iteration of the loop.)

17

18 // NOTE: Compare this to two_sum_hash.cpp, which implements the same algorithm

19 // for arbitrary input arrays and prints all matching pairs instead of just the

20 // first.

21

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

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

24

25 #include <map>

26 #include <string>

27 #include <cstdlib>

28 #include <iostream>

29

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

31 char *endptr = NULL;

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

33

34 long lookfor, num, index = 0;

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

36 std::map<long, long>::const_iterator iter;

37 std::string s;

38

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

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

41 lookfor = target - num;

42 if ( ( iter = hash.find(lookfor) ) != hash.end() ) {

43 std::cout << num << " " << lookfor << " (indices " << index << ", " << (*iter).second << ")" << std::endl;

44 exit(EXIT_SUCCESS);

45 }

46 hash[num] = index++;

47 }

48 exit(EXIT_FAILURE);

49 }