学步园

3Sum Closest
描述
Given an array S of n integers, find three integers in S such that the sum is closest to a given number,
target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

For example, given array S = {-1 2 1 -4}, and target = 1.The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

主要利用了加逼的思想，算法里面数组需要先排序，我假设是已经排好的，实际实现可以换成Vector容器，使用sort

进行排序，然后改写如下函数即可。

#include <iostream>
#include <map>
#include <vector>
#include <string>

using namespace std;

class Solution
{
public:
	//array 已经按照升序排好了,返回最接近target值得结果，不需要下标。
	int Sum3Closet(int * array, int length, int target)
	{
		int sum;
		int result;
		unsigned int distance = 0xffffffff;
		int i,a,b;

		for(i=0; i<length-2; i++)
		{
			a = i+1;
			b = length-1;		
			while( a < b )
			{
				sum = array[i]+array[a]+array[b];
				if( abs(sum - target) < distance )
				{
					result = sum;
					distance = abs(sum - target);
				}

				if( sum > target )
				<span style="white-space:pre">	</span>b--;
				else if(sum < target)
					a++;
				else 
					return sum;
			}
		}
		return result;
	}
};


int main()
{
	//int array[12] = {-1, 2, 4, 9, 10, 15, 24, 33, 35, 67, 100, 101};
	int array[4] = {-1,2,1,4};
	Solution s;
	int ret;
	ret = s.Sum3Closet(array, 4, 0);
	cout<<ret<<endl;
	return 0;
}