Solution to the LeetCode Two Sum problem.

There is a number of ways to do this:

- Naive – explore all pairs of two – \(O(n^2)\)
- Sort and use two pointers – \(O(n\log{n})\)
- Use a hashmap – \(O(n)\), but requires some extra bookkeeping.

In this solution, I’ll use a hashmap, since I’ll use the sorting method for the later questions on Three-Sum and Four-Sum. The hashmap solution works as follows – add all the elements one by one to the hashmap. Then, traverse the array again, and for each element \(i\), check if \(c-i\) (where \(c\) is the desired sum) is in the hashmap. If so, we found a match. The issue is we need to keep track of the indices where each element appeared at, otherwise we’ll get false positives for cases such as \([5,2]\) and we are looking for a sum \(10\). The algorithm will say a solution exists, when it clearly doesn’t.