首页 > 代码库 > [LeetCode ] Two Sum
[LeetCode ] Two Sum
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where
index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not
zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
分析：
（1）O(nlogn)。排序，然后两个指针一前一后夹逼。因为题中说明了只有一对答案，因此不需要考虑重复的情况。
（2）O(n)。哈希表。将每个数字放在map中，历遍数组，如果出现和数组中的某一个值相加为target的时候，break。这个方法同样适用于多组解的情况。
方法1 code
1 struct Node 2 { 3 int val; 4 int idx; 5 Node(){} 6 Node(int v, int i):val(v), idx(i){} 7 }; 8 9 bool compare(const Node &l, const Node &r)10 {11 return l.val < r.val;12 }13 14 class Solution {15 public:16 vector<int> twoSum(vector<int> &numbers, int target) {17 // Start typing your C/C++ solution below18 // DO NOT write int main() function19 vector<Node> tmp;20 for(int i = 0; i < numbers.size(); i++)21 tmp.push_back(Node(numbers[i], i + 1));22 sort(tmp.begin(), tmp.end(), compare);23 24 int i = 0;25 int j = numbers.size() - 1;26 while(i < j)27 {28 int sum = tmp[i].val + tmp[j].val;29 if (sum == target)30 {31 vector<int> result;32 int minIndex = min(tmp[i].idx, tmp[j].idx);33 int maxIndex = max(tmp[i].idx, tmp[j].idx);34 result.push_back(minIndex);35 result.push_back(maxIndex);36 return result;37 }38 else if (sum < target)39 i++;40 else41 j--;42 }43 }44 };
方法2 code：
1 class Solution { 2 public: 3 map<int,int> m; 4 vector<int> twoSum(vector<int> &numbers, int target) 5 { 6 vector<int> v; 7 for(vector<int>::size_type st = 0; st < numbers.size(); st ++) 8 { 9 map<int,int>::iterator it = m.find(target-numbers[st]);10 if(it == m.end())11 m.insert(map<int,int>::value_type(numbers[st], st+1));12 else13 {14 //first insert‘s index is smaller15 v.push_back(it->second);16 v.push_back(st+1);17 return v;18 }19 }20 }21 };
下面的code答案是错误的：
其做法：1 将所有值和index加入mapping中
2 在mapping中查找
错误原因 ： [4 , 5, 6 ,7] target = 8, 会输出 1,1 原因是 maping中有pair(4, 1) 当查找 target - 4 =4时会查到，所以报错，因此，要边查找边插入。
1 class Solution { 2 public: 3 vector<int> twoSum(vector<int> &num, int target) { 4 unordered_map<int, int> mapping; 5 vector<int> result; 6 for (int i = 0; i < num.size(); i++) { 7 mapping[num[i]] = i; 8 } 9 for (int i = 0; i < num.size(); i++) {10 const int gap = target - num[i];11 if (mapping.find(gap) != mapping.end()) {12 result.push_back(i + 1);13 result.push_back(mapping[gap] + 1);14 break;15 }16 }17 return result;18 }19 };