For an unsorted array A of n integers, and a target integer t, the goal is to determine whether or not there are two numbers x, y in A satisfying x + y = t ².

This problem can be solved by brute-force search - by trying all possibilities for x and y and checking if any of them work. That would be a quadratic-time algorithm (O (n²)), since there are n choices for x and y.

Most of the work in this algorithm boils down to repeated lookups, so one way to improve it is to use a hash table. A good hash table provides Insert and Lookup operations in constant time, and we can use it to solve the 2-SUM problem in linear time.

The input file contains 1 million integers, both positive and negative (there might be some repetitions!).This is your array of integers, with the ith row of the file specifying the ith entry of the array.

Your task is to compute the number of target values t in the interval [-10000,10000] (inclusive) such that there are distinct numbers x,y in the input file that satisfy x + y = t.

The implementation of the solution above is O(n) for a single target t, but this exercise requires testing all values of t in the interval [-10000,10000], resulting in roughly 20 billion lookups. For that reason, even though the hash table speeds things up, the algorithm can take a considerably long time to calculate the answer.

An alternative implementation is presented in the file 2-sum-alternative.js, following a different approach:

• Sort the array;
• Iterate using two pointers: one from beginning to end, another from the end to beginning of the array, until they cross each other;
• If values given by the pointers fall inside the given interval, re-iterate internally.