本文共 2834 字，大约阅读时间需要 9 分钟。

class Solution {public:	struct Node	{		int num, idx;		Node(int _num = 0, int _idx = 0):num(_num),idx(_idx){}		bool operator < (const Node& orh) const		{   			if(num == orh.num)				return idx < orh.idx;			else return num < orh.num;		}	};    vector
   
     twoSum(vector
    
      &numbers, int target) {        // Start typing your C/C++ solution below        // DO NOT write int main() function                //step 0. get an arry record the num and index of every element        //step 1. sort the array and then         //step 2. enumerate every element numbers[i] in the array        //step 3. using binary search to find if there is an element equal to target-numbers[i]        //Time complexity Analysis: O(nlgn)                vector
     
       nodes(numbers.size());//step 0        for(int i = 0; i < numbers.size(); ++i)            nodes[i] = Node(numbers[i], i);                    sort(nodes.begin(), nodes.end());//step 1        for(int i = 0; i < nodes.size(); ++i)//step 2        {            int v2 = target-nodes[i].num;            //step 3            int l = min(i+1, (int)nodes.size()-1);            int r = nodes.size()-1;            while(l <= r)            {                int mid = (l+r)/2;                if(nodes[mid].num > v2)                    r = mid-1;                else if(nodes[mid].num == v2)                {                    vector
      
        twoSum(2);                    twoSum[0] = min(nodes[i].idx+1, nodes[mid].idx+1); twoSum[1] = max(nodes[i].idx+1, nodes[mid].idx+1);                    return twoSum;                }                else l = mid+1;            }        }    }};
      
     
    
   

second time:

class Solution {public:    struct Node    {        int index;        int value;        Node(int _index = 0, int _value = 0):index(_index),value(_value){};        bool operator < (const Node& orh) const        {            return value < orh.value;        }    };    vector
   
     twoSum(vector
    
      &numbers, int target) {        // Start typing your C/C++ solution below        // DO NOT write int main() function        vector
     
       nodes(numbers.size());        for(int i = 0; i < numbers.size(); ++i)            nodes[i].index = i, nodes[i].value = numbers[i];                    sort(nodes.begin(), nodes.end());        int idx1 = 0;        int idx2 = nodes.size()-1;                while(idx1 < idx2)        {            int curSum = nodes[idx1].value+nodes[idx2].value;            if(curSum > target)                idx2--;            else if(curSum < target)                idx1++;            else break;        }                //save & return         vector
      
        result;        result.push_back(min(nodes[idx1].index+1, nodes[idx2].index+1));        result.push_back(max(nodes[idx1].index+1, nodes[idx2].index+1));        return result;    }};
      
     
    
   

转载地址：http://dhxti.baihongyu.com/