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,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 

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 presorted 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, presorting the array reduces the complexity to $O(N \cdot \log N)$,
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 

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)$.