1.1 --- a/two_sum/two_sum.cpp	Fri May 01 16:28:22 2015 -0500
     1.2 +++ b/two_sum/two_sum.cpp	Mon May 04 12:32:58 2015 -0500
     1.3 @@ -15,6 +15,10 @@
     1.4  // into the hash, which adds only a small constant to the running time per
     1.5  // iteration of the loop.)
     1.6  
     1.7 +// NOTE: Compare this to two_sum_hash.cpp, which implements the same algorithm
     1.8 +// for arbitrary input arrays and prints all matching pairs instead of just the
     1.9 +// first.
    1.10 +
    1.11  // Usage: Pass the target value as a command line option, and the number array as
    1.12  // values on stdin, one item per line.
    1.13  

     2.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     2.2 +++ b/two_sum/two_sum_hash.cpp	Mon May 04 12:32:58 2015 -0500
     2.3 @@ -0,0 +1,65 @@
     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: Add the input numbers to a hash with the number as the hash key,
     2.8 +// and it's index position in the input as the hash value.
     2.9 +
    2.10 +// At each step we can do an O(1) lookup in the hash to see if target - num has
    2.11 +// already been added to the hash.  If it has, we terminate processing and print
    2.12 +// the two numbers (along with their indices).  Otherwise we add num to the hash
    2.13 +// and loop back to read the next input number.
    2.14 +
    2.15 +// Overall performance is O(N) in the worst case, since in that case we must
    2.16 +// process each input item exactly once.  (For each item, we perform one lookup
    2.17 +// into the hash, which adds only a small constant to the running time per
    2.18 +// iteration of the loop.)
    2.19 +
    2.20 +// Usage: Pass the target value as a command line option, and the number array as
    2.21 +// values on stdin, one item per line.
    2.22 +
    2.23 +#include <map>
    2.24 +#include <string>
    2.25 +#include <cstdlib>
    2.26 +#include <iostream>
    2.27 +#include <vector>
    2.28 +
    2.29 +void two_sum( std::vector<long> vec, long target ) {
    2.30 +    std::map<long, long> hash;
    2.31 +
    2.32 +    for ( long i=0; i < vec.size(); i++ ) {
    2.33 +        hash[vec[i]] = i;
    2.34 +        }
    2.35 +
    2.36 +    long lookfor;
    2.37 +    long i = 0;
    2.38 +    std::map<long, long>::iterator it;
    2.39 +    while ( i < vec.size() ) {
    2.40 +        if ( vec[i] <= target/2 ) {
    2.41 +            lookfor = target - vec[i];
    2.42 +            if ( ( ( it = hash.find(lookfor) ) != hash.end() ) && ( (*it).first != vec[i] ) ) {
    2.43 +                std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << (*it).second << ")" << std::endl;
    2.44 +                }
    2.45 +            }
    2.46 +        i++;
    2.47 +        }
    2.48 +    }
    2.49 +
    2.50 +int main( int argc, char **argv ) {
    2.51 +    char *endptr = NULL;
    2.52 +    long target = strtol( argv[1], &endptr, 10);
    2.53 +
    2.54 +    std::vector<long> vec;
    2.55 +    long num;
    2.56 +    std::string s;
    2.57 +
    2.58 +    while ( std::cin >> s ) {
    2.59 +        num = strtol( s.c_str(), &endptr, 10);
    2.60 +        vec.push_back(num);
    2.61 +        }
    2.62 +
    2.63 +    two_sum( vec, target );
    2.64 +
    2.65 +    exit(EXIT_SUCCESS);
    2.66 +    }
    2.67 +
    2.68 +

     3.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     3.2 +++ b/two_sum/two_sum_sort.cpp	Mon May 04 12:32:58 2015 -0500
     3.3 @@ -0,0 +1,65 @@
     3.4 +// Problem: given an input array of numbers, and a target value, find all pairs
     3.5 +// of numbers in the input which sum to the target value.
     3.6 +
     3.7 +// Solution: Sort the input data.  We can now use binary search to look up target numbers.
     3.8 +
     3.9 +// Time performance is O(N log N) for the lookup, and varies for the sort,
    3.10 +// though here it is also O(N log N) giving O(N log N) overall performance.
    3.11 +// Space complexity if O(1), though, since no extra space is needed for the operations.
    3.12 +
    3.13 +// Usage: Pass the target value as a command line option, and the number array as
    3.14 +// values on stdin, one item per line.
    3.15 +
    3.16 +#include <algorithm>
    3.17 +#include <vector>
    3.18 +#include <string>
    3.19 +#include <cstdlib>
    3.20 +#include <iostream>
    3.21 +
    3.22 +long binary_search( std::vector<long> vec, long lookfor, long min, long max ) {
    3.23 +    while ( max >= min ) {
    3.24 +        long mid = min + (max - min) / 2;
    3.25 +        if ( vec[mid] == lookfor )
    3.26 +            return mid;
    3.27 +        else if ( vec[mid] > lookfor )
    3.28 +            max = mid - 1;
    3.29 +        else
    3.30 +            min = mid + 1;
    3.31 +        }
    3.32 +    return -1;
    3.33 +    }
    3.34 +
    3.35 +void two_sum( std::vector<long> vec, long target ) {
    3.36 +    std::sort( vec.begin(), vec.end() );
    3.37 +
    3.38 +    long lookfor;
    3.39 +    long i = 0;
    3.40 +    while ( vec[i] <= target/2 ) {
    3.41 +        lookfor = target - vec[i];
    3.42 +        long pos = binary_search( vec, lookfor, 0, vec.size()-1 );
    3.43 +        if ( pos != -1 && pos != i ) {
    3.44 +            std::cout << vec[i] << " " << lookfor << " (indices " << i << ", " << pos << ")" << std::endl;
    3.45 +            }
    3.46 +        i++;
    3.47 +        }
    3.48 +    }
    3.49 +
    3.50 +int main( int argc, char **argv ) {
    3.51 +    char *endptr = NULL;
    3.52 +    long target = strtol( argv[1], &endptr, 10);
    3.53 +
    3.54 +    std::vector<long> vec;
    3.55 +    long num;
    3.56 +    std::string s;
    3.57 +
    3.58 +    while ( std::cin >> s ) {
    3.59 +        num = strtol( s.c_str(), &endptr, 10);
    3.60 +        vec.push_back(num);
    3.61 +        }
    3.62 +
    3.63 +    two_sum( vec, target );
    3.64 +
    3.65 +    exit(EXIT_SUCCESS);
    3.66 +    }
    3.67 +
    3.68 +