44_和为S的两个数字

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

/*
题目描述:
输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。
*/

class Solution 
{
public:
	//很笨的方法			O(N)
	vector<int> FindNumbersWithSum(vector<int> array, int sum)
	{
		vector<int> ret;
		if (array.empty())
		{
			return ret;
		}
		for (size_t i = 0; i < array.size(); ++i)
		{
			if (array[i] >= sum)
			{
				break;
			}
			int val1 = array[i];
			for (size_t j = i; j < array.size(); ++j)
			{
				if (array[j] >= sum)
				{
					break;
				}
				int val2 = array[j];
				if (val1 + val2 == sum)
				{
					ret.push_back(val1);
					ret.push_back(val2);
					return ret;
				}
			}
		}
		return ret;
	}

  //改进 
  //O(N)
	vector<int> FindNumbersWithSumImprove(vector<int> array, int sum)   
	{
		vector<int> ret;
		int begin = 0;
		int end = array.size() - 1;
		while (begin < end)
		{
			if (array[begin] * array[end] == sum)
			{
				ret.push_back(array[begin]);
				ret.push_back(array[end]);
				break;
			}
			while (array[begin] * array[end] < sum)
			{
				++begin;
			}
			while (array[begin] * array[end] > sum)
			{
				--end;
			}
		}
		return ret;
	}
};

void Test()
{
	vector<int> ivec= { 1, 2, 3, 4, 5, 6 ,7 ,8, 9, 10 };
	vector<int> ret = Solution().FindNumbersWithSum(ivec, 11);
	for (int &i : ret)
	{
		cout << i << " ";
	}
	cout << endl;
}
int main()
{
	Test();
	return 0;
}