首页 > 代码库 > Leetcode 线性表 Two Sum
Leetcode 线性表 Two Sum
本文为senlie原创，转载请保留此地址：http://blog.csdn.net/zhengsenlie
Two Sum
Total Accepted: 19206 Total Submissions: 103959Given 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： --> 错，因为题目要求返回下标。
1.排序
2.两个下标，一个指向头，一个指向尾
3.如果下标指向的两个元素相加大于给定的数，尾下标减一
如果小于，头下标加一
思路2： hash
1.用hash存储每个数的下标
2.数组,看hash[target-num[i]]是否存在
复杂度：时间O(n)， 空间O(n)
class Solution {
public:
vector<int> twoSum(vector<int> &num, int target){
map<int, int> m;
vector<int> result;
for(int i = 0; i < num.size(); i++) m[num[i]] = i;
for(int i = 0; i < num.size(); i++){
int j = m[target - num[i]];
if(j && j != i){
result.push_back(i + 1);
result.push_back(j + 1);
return result;
}
}
}
};
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。