For two sum, we can sort the array and scan from two ends.
Then space O(1), time O(nlogn)
For here, it only accepts index. So we cant sort it as the index will change. Use hash table to record it.
Then space O(n), time O(n)
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int> &numbers, int target) { 4 vector<int> result(2); 5 unordered_map<int, int> record; 6 for (int i = 0; i < numbers.size(); i++) { 7 if (record[target - numbers[i]]) { 8 result[0] = record[target - numbers[i]]; 9 result[1] = i+1; 10 return result; 11 } else record[numbers[i]] = i+1; 12 } 13 } 14 };
原文：http://www.cnblogs.com/shuashuashua/p/4363425.html