1.1 --- a/two_sum/two_sum_hash.cpp	Mon May 04 12:32:58 2015 -0500
     1.2 +++ b/two_sum/two_sum_hash.cpp	Mon May 04 15:20:26 2015 -0500
     1.3 @@ -4,23 +4,23 @@
     1.4  // Solution: Add the input numbers to a hash with the number as the hash key,
     1.5  // and it's index position in the input as the hash value.
     1.6  
     1.7 -// At each step we can do an O(1) lookup in the hash to see if target - num has
     1.8 -// already been added to the hash.  If it has, we terminate processing and print
     1.9 -// the two numbers (along with their indices).  Otherwise we add num to the hash
    1.10 -// and loop back to read the next input number.
    1.11 +// For each value in the array, check to see if (target - value) is also in the
    1.12 +// hash and if so print the pair of nubmers.  We need not consider values
    1.13 +// greater than target/2 since this would generate a duplicate pair when we
    1.14 +// eventually come across (target - value) itself in the array.
    1.15  
    1.16 -// Overall performance is O(N) in the worst case, since in that case we must
    1.17 -// process each input item exactly once.  (For each item, we perform one lookup
    1.18 -// into the hash, which adds only a small constant to the running time per
    1.19 -// iteration of the loop.)
    1.20 +// We are using an extra O(N) amount of memory for the hash table, but doing so
    1.21 +// gives us O(1) lookup time to see if (target - value) is also in the array, so
    1.22 +// once the hash is built in O(N) time we need only another O(N) amount of time
    1.23 +// to find all pairs, yielding an overall O(N) running time.
    1.24  
    1.25  // Usage: Pass the target value as a command line option, and the number array as
    1.26  // values on stdin, one item per line.
    1.27  
    1.28 +#include <cstdlib>
    1.29 +#include <iostream>
    1.30  #include <map>
    1.31  #include <string>
    1.32 -#include <cstdlib>
    1.33 -#include <iostream>
    1.34  #include <vector>
    1.35  
    1.36  void two_sum( std::vector<long> vec, long target ) {
    1.37 @@ -36,7 +36,7 @@
    1.38      while ( i < vec.size() ) {
    1.39          if ( vec[i] <= target/2 ) {
    1.40              lookfor = target - vec[i];
    1.41 -            if ( ( ( it = hash.find(lookfor) ) != hash.end() ) && ( (*it).first != vec[i] ) ) {
    1.42 +            if ( ( ( it = hash.find(lookfor) ) != hash.end() ) && ( (*it).second != i ) ) {
    1.43                  std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << (*it).second << ")" << std::endl;
    1.44                  }
    1.45              }

     2.1 --- a/two_sum/two_sum_sort.cpp	Mon May 04 12:32:58 2015 -0500
     2.2 +++ b/two_sum/two_sum_sort.cpp	Mon May 04 15:20:26 2015 -0500
     2.3 @@ -1,7 +1,10 @@
     2.4  // Problem: given an input array of numbers, and a target value, find all pairs
     2.5  // of numbers in the input which sum to the target value.
     2.6  
     2.7 -// Solution: Sort the input data.  We can now use binary search to look up target numbers.
     2.8 +// Solution: Sort the input data.  For each value in the array, use binary
     2.9 +// search to see if (target - value) is also in the array, and if so print the
    2.10 +// pair of numbers.  We need not consider values greater that target/2 since 
    2.11 +// the the data is sorted, and (target - value) would have already been checked.
    2.12  
    2.13  // Time performance is O(N log N) for the lookup, and varies for the sort,
    2.14  // though here it is also O(N log N) giving O(N log N) overall performance.
    2.15 @@ -11,10 +14,10 @@
    2.16  // values on stdin, one item per line.
    2.17  
    2.18  #include <algorithm>
    2.19 -#include <vector>
    2.20 -#include <string>
    2.21  #include <cstdlib>
    2.22  #include <iostream>
    2.23 +#include <string>
    2.24 +#include <vector>
    2.25  
    2.26  long binary_search( std::vector<long> vec, long lookfor, long min, long max ) {
    2.27      while ( max >= min ) {