首页 > 代码库 > 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;            }        }    }};
View Code

对每一个数a,target-a,在原数组中二分查找,这样时间便是nlogn。下标问题可新建一个数组,新存储一个标,这样排序后也能找到原来的下标。

Two Sum