The two sum problem require us to find two elements in an arrays that sum to a given value. There are different approach to solve the problem depending on whether the arrays is sort or not.
A naive solution looks something like this
This solution checks all combinations between two number and compare the result to the sum value, the time complexity is $O(N^2)$.
If we are given a sorted array we can experiment and solve the problem with a binary search. For each element $x$ in the array we need to check if an element $sum - x$ exists.
With this we are performing a binary search for every elements, the total running time would be $O(N\log N)$.
If the arrays is sorted we can also solve code a linear solution for the problem. This new approach use a sub-interval of the array and compare the sum of its leftmost and rightmost element (the limits of the interval) to the target sum. This require the arrays to be sorted because
- If the sum is greater that the target, we can obtain a smaller sum by shrinking the interval on the right (excluding larger value)
- If the sum is smaller the interval is shrunk on the left (to leave out smaller elements)
The running time for this solution is obviously $O(N)$
If the array is not sorted, a general approach to solve the problem could be using an hash set. While iterating over all elements for each element $x$ I check if an element with value $sum-x$ exists, if it doesn’t exists I just put the element in the set.
The running time is still “linear”, although some overhead is caused by the hash set/table, both for the time and memory usage.
The solutions above only return if two elements that sum up to a certain value exists. The following snippet counts how many of those pair exists
The idea is pretty straightforward: for every element, perform a binary search of the complementary element that sums up to the target value. Although the algorithm itself has a running time of $O(N\cdot \log N)$ because of sorting, it’s possible to make it run a little bit faster by avoid recalculating the result for repeating elements. The only thing to be careful about is the case when $element + element = target$, in that case, as the following repeating element are considered, is necessary to decrease the partial solution by one, to account for the element that is before the current.