问题：找出数组中两个数之和等于一个给定目标数。并输出这两个数在数组中的下标。
1.暴力O(n^2)，两个for循环查找，TLE。
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int> &numbers, int target) { 4 5 vector<int> ans; 6 for (int i = 0; i < numbers.size()-1; i++) 7 { 8 for (int j = i+1; j < numbers.size(); j++) 9 { 10 if (numbers[i] + numbers[j] == target) 11 { 12 ans.push_back(i+1); 13 ans.push_back(j+1); 14 return ans; 15 } 16 } 17 } 18 } 19 };
2.O(n*logn),用一个pair，记录index和num，然后排序num，用两个指针向中间移动寻找答案
如果 sum = l.num + r.num, 那么 l.index 和 r.index 就是答案。注意答案index的顺序。
1 int cmp(const pair<int, int> &a, const pair<int, int> &b) { 2 if (a.first == b.first) return a.second < b.second; 3 else return a.first < b.first; 4 } 5 6 class Solution { 7 public: 8 9 vector<int> twoSum(vector<int> &numbers, int target) { 10 11 assert(numbers.size() >= 2); 12 13 vector<int> ans; 14 vector< pair<int, int> > PairNumber; 15 for (int i = 0; i < numbers.size(); i++) { 16 PairNumber.push_back(make_pair(numbers[i], i+1)); 17 } 18 19 sort(PairNumber.begin(), PairNumber.end(), cmp); 20 21 int l = 0, r = PairNumber.size()-1; 22 while (l < r) { 23 int sum = PairNumber[l].first + PairNumber[r].first; 24 if (sum == target) { 25 ans.push_back(min(PairNumber[l].second, PairNumber[r].second)); 26 ans.push_back(max(PairNumber[l].second, PairNumber[r].second)); 27 break; 28 } 29 else if (sum < target) { 30 l++; 31 } 32 else { 33 r--; 34 } 35 } 36 return ans; 37 } 38 };
3.O(n)，用hash来做。C++中使用map,O（nlogn）。在边进行hash当前数numbers[i]的时候边判断是否出现target-numbers[i]。
C++:
1 class Solution { 2 public: 3 4 vector<int> twoSum(vector<int> &numbers, int target) { 5 6 vector<int> ans; 7 map<int, int> hash; 8 for (int i = 0; i < numbers.size(); ++i) { 9 if (hash.find(target-numbers[i]) != hash.end()) { 10 ans.push_back(hash[target-numbers[i]]); 11 ans.push_back(i+1); 12 break; 13 } 14 else { 15 hash.insert(make_pair(numbers[i], i+1)); 16 } 17 18 } 19 return ans; 20 } 21 };
Java:
1 import java.util.Hashtable; 2 public class Solution { 3 public int[] twoSum(int[] numbers, int target) { 4 assert (numbers.length >= 2); 5 int ans[] = new int[2]; 6 Hashtable<Integer, Integer> hash= new Hashtable<Integer, Integer>(); 7 for (int i = 0; i < numbers.length; i++) { 8 if (hash.get(target-numbers[i]) != null) { 9 ans[0] = hash.get(target-numbers[i]); 10 ans[1] = i+1; 11 break; 12 } 13 else { 14 hash.put(numbers[i], i+1); 15 } 16 } 17 return ans; 18 } 19 }