# Find two nums so that they add up to a specific num

In leetcode practice, one simple practice is that given an array of integers, return the two indices of the two numbers such that they add up to a specific number. For example, a[] = {2, 3, 6, 9} and target = 6, we should return 1, 2(the indices of 3, 6). An intuitive algorithm is to write two for loops, like,

However, it is of $O(N^2)$ computation complexity, which is unbearable in practice. Yes, a much more fast algorithm is desirable and essential. So, let’s step further and think that what if the array a[] is pre-sorted so that the second for loop is ignorable and the computation complexity callapses into $O(N)$? Sorting an array usually requires $O(\log N)$ complexity\,(like fast sorting). Therefore, pre-sorting the array reduces the complexity to $O(N \cdot \log N)$,

No, that is not enough. Does the sorting $O(\log N)$ complexity can be further eliminated? Remember that the retrieval complexity of harsh table is $O(1)$, why not first storing those numbers into a harsh table so that the overal complexity is reduced to $O(N)$.