首页 > 代码库 > Two Sum
Two Sum
struct node{ int n; int value;};bool cmp(node a,node b){ return a.value<b.value;}class Solution {public: vector<int> twoSum(vector<int> &numbers, int target) { vector<node> a; vector<int> result; for(int i=0;i<numbers.size();i++) { a.push_back(node{i+1,numbers[i]}); } sort(a.begin(),a.end(),cmp); for(int i=0;i<a.size();i++) { int l=0,r=numbers.size(); int key=target-a[i].value; while(l<r) { int m=l+(r-l+1)/2; if(a[m].value=http://www.mamicode.com/=key&&m!=i) { result.push_back(a[i].n); result.push_back(a[m].n); sort(result.begin(),result.end()); return result; } if(a[m].value<key) l=m; if(a[m].value>key) r=m-1; } } }};
对每一个数a,target-a,在原数组中二分查找,这样时间便是nlogn。下标问题可新建一个数组,新存储一个标,这样排序后也能找到原来的下标。
Two Sum
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。