首页 > 代码库 > LeetCode:two sum
LeetCode:two sum
题目：
如果采取暴力搜索，复杂度为O（n2），会超时
解法1：
构建Node类，存储输入的数据和它们的下标。
用sort按升序排序（其中lambda可以写成一个返回值为bool类型的函数）。
设置i和j，分别指向容器的头和尾。如果和大于target，尾向前移，如果和小于target，头向后移。直至找出和等于target的两个值。
将其原始坐标加入结果容器中。
复杂度为O（nlogn）。
1 #include<vector> 2 #include<iostream> 3 #include<algorithm> 4 using namespace std; 5 6 struct Node 7 { 8 int num; 9 int index;10 };11 12 class Solution {13 public:14 vector<int> twoSum(vector<int> &numbers, int target) {15 vector<Node> data;16 vector<int> result;17 18 for(int i=0;i!=numbers.size();++i)19 {20 Node node;21 node.num=numbers[i];22 node.index=i+1;23 data.push_back(node);24 }25 26 sort(data.begin(),data.end(),[](const Node &a,const Node &b){return a.num<=b.num;});27 28 int i=0,j=numbers.size()-1;29 30 while(i!=j)31 {32 int sum=data[i].num+data[j].num;33 34 if(sum<target)35 {36 ++i;37 }38 else if(sum>target)39 {40 --j;41 }42 else43 {44 break;45 }46 }47 48 if(data[i].index>data[j].index){49 result.push_back(data[j].index);50 result.push_back(data[i].index);51 }52 else53 {54 result.push_back(data[i].index);55 result.push_back(data[j].index);56 }57 58 return result;59 }60 };
解法2：
的
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。