首页 > 代码库 > [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
这道题一看就知道用暴力搜索肯定没问题，而且猜到OJ肯定不会允许用暴力搜索这么简单的方法，于是去试了一下，果然是Time Limit Exceeded，这个算法的时间复杂度是O(n^2)，代码如下：
/** * Time Limit Exceeded */class Solution {public: vector<int> twoSum(vector<int> &numbers, int target) { vector<int> res; for (int i = 0; i < numbers.size(); ++i) { for (int j = i + 1; j < numbers.size(); ++j) { if (numbers[j] + numbers[i] == target) { res.push_back(i + 1); res.push_back(j + 1); } } } return res; }};
那么只能想个O(n)的算法来实现，参考了网友的解法，发现需要用map数据类型，查找复杂度是O(lgn)，相当于二分查找法的效率，非常赞。整个实现步骤为：先遍历一遍数组，建立map数据，然后再遍历一遍，开始查找，找到则记录index。代码如下：
class Solution {public: vector<int> twoSum(vector<int> &numbers, int target) { vector<int> res; map<int, int> numMap; for (int i = 0; i < numbers.size(); ++i) { numMap[numbers[i]] = i; } for (int i = 0; i < numbers.size(); ++i) { int tmp = target - numbers[i]; if (numMap.find(tmp) != numMap.end() && numMap[tmp] != i) { res.push_back(i + 1); res.push_back(numMap[tmp] + 1); break; } } return res; }};
[LeetCode] Two Sum 两数之和
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。