学步园

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

class Solution1 {
public:
    vector<int> twoSum(vector<int> &numbers, int target) 
	{
		vector<int> v;
    	for(int i = 0; i < numbers.size(); ++i)
		{
			for(int j = i + 1; j < numbers.size(); ++j)
			{
				if(numbers[i] + numbers[j] == target)
				{
					v.push_back(i + 1);
					v.push_back(j + 1);
					return v;
				}
			}
		}    
    }
};

struct node
{
	int data;
	int pos;
};

bool cmp(node a, node b)
{
	return a.data < b.data;
}

class Solution {
public:
    vector<int> twoSum(vector<int> &numbers, int target) 
	{
		vector<int> v;
		vector<node> v1;
		int i, val, len = numbers.size();

		for (i = 0; i < len; ++i)
		{
			node tmp;
			tmp.data = numbers[i];
			tmp.pos = i;
			v1.push_back(tmp);
		}
 
		sort(v1.begin(), v1.end(), cmp);
		
    	for(i = 0; i < len; ++i)
		{
		    val = target - v1[i].data;
		    int lhs = i + 1, rhs = len - 1;
		    
			while(lhs <= rhs)
			{
			    int mid = (lhs + rhs) >> 1;
			    
			    if(v1[mid].data == val)
			    {
					if(v1[i].pos < v1[mid].pos)
					{
						v.push_back(v1[i].pos + 1);
						v.push_back(v1[mid].pos + 1);
					}
					else
					{
						v.push_back(v1[mid].pos + 1);
						v.push_back(v1[i].pos + 1);
					}
					return v;
			    }
			    
			    if(v1[mid].data < val)
			    {
			        lhs = mid + 1;
			    }
			    else
			    {
			        rhs = mid - 1;
			    }
			}
		}
		return v;
    }
};

int main(void)
{
	int a[] = {
		3, 2, 4
	};
	vector<int> vs(a, a + 3);
	Solution s;
	vector<int> re = s.twoSum(vs, 6);
	
	cout << re[0] << " " << re[1] << endl;
	 
	return 0;
}