Two Sum
It is not easy to write Two-Sum right for the first time. A few points deserve us
attentions:
- Is the array sorted or not?
- Does the array contain duplicates?
- Shall we return values or indexes? (sorted?)
Solution - HashTable
A typical solution is to create an inverted index for each number and search for the index of (target - nums[index]) if any. This takes O(n) space and O(n) time.
If the array contains duplicates, the inverted index should be built by
HashMap<Integer, List<Integer>> to contain all possible indexes.
One corner case would be "[3,1] 6". It is easy to use 3 twice so check the two numbers do not share the same index before moving forward.
Solution - Two Pointer
Another typical solution is to sort the array first and use two pointers to find the target sum by a greedy approach. This takes O(nlogn) for sorting, and O(n) for finding the index pair, which is totally O(nlogn) for time. And this takes O(1) space.
