3Sum Closest 【leetcode】

#include<string>
#include<iostream>
#include<stack>
#include<vector>
#include<set>
#include<algorithm>
using namespace std;

int threeSumClosest(vector<int> &num, int target) {
	sort(num.begin(), num.end());
	const int N = num.size();
	int minDis = INT_MAX;
	int result = 0;
	for (int i = 0; i < N; ++i)
	{
		if (i > 0 && num[i] == num[i - 1]) continue;
		int s = i + 1, e = N - 1;
		while (s < e)
		{
			int curSum = num[s] + num[e] + num[i];
			int curDis = abs(curSum - target);
			if (curDis < minDis)
			{
				minDis = curDis;
				result = curSum;
			}
			if (curSum == target)
			{
				return target;
			}
			else if (curSum > target)
			{
				while (s < --e && num[e] == num[e + 1]);
			}
			else
			{
				while (++s < e && num[s] == num[s - 1]);
			}
		}
	}
	return result;
}

int threeSumClosest1(vector<int> &num, int target)
{
	sort(num.begin(),num.end());
	int i = 0;
	int s, e, currentmin = INT_MAX, result=0;
	for (i = 0; i < num.size(); i++)
	{
		s = i + 1;
		e = num.size() - 1;
		while (s<e)
		{
			int sum = num[i] + num[s] + num[e];
			int abssum = abs(sum - target);
			if (abssum < currentmin)
			{
				currentmin = abssum;
				result = sum;
			}
			if (sum == target)
				return target;
			else if (sum > target)
			{
				e--;
				while (num[e] == num[e + 1])
				{
					if (s < e)
					{
						e--;
					}
					else
					{
						break;
					}
				}
					
			}
			else 
			{
				s++;
				while (num[s] == num[s - 1])
				{
					if (s < e)
					{
						s++;
					}
					else
					{
						break;
					}
				}
			}
		}

	}
	return result;
}

int main()
{
	vector<int> nums = { 100,50,20,-1, 2, 1, -4 };
	int t = 1;
	cout << threeSumClosest1(nums,t) << endl;
}

思路：先给数组内元素排序，选择一个元素num[i]，对i下标的元素找开始和结尾下标，分别为s = i + 1, e = N - 1; 那么curSum = num[s] + num[e] + num[i]; 算出curSum和target的差值的绝对值，要是小于最小值，那么更新最小值。之后判断curSum和target的大小关系，若相等，则返回target，此时两者差值最小，为0；若curSum > target，则尾下标e自减，即curSum的值变小，这时判断num[e] == num[e + 1]是否成立，成立说明两者相等，即存在相同值，那么尾下标e还要继续自减，当两者不等时退出循环，且当s>=e时也要退出循环； curSum < target 的情况同理

3Sum Closest 【leetcode】

原文：http://my.oschina.net/a20092173/blog/516839