#include <cstdlib>
class Solution
{
public:
	int threeSumClosest(vector<int> &nums, int target)
	{
		sort(nums.begin(), nums.end());
		int cur, left, right;
		cur = 0;
		int closest = nums[0] + nums[1] + nums[2];
		while (cur < nums.size() - 2)
		{
			left = cur + 1;
			right = nums.size() - 1;
			int n;
			while (left < right)
			{
				n = nums[cur] + nums[left] + nums[right];
				if (abs(target - n) < abs(target - closest))
				{
					closest = n;
				}
				if (n == target)
				{
					break;
				}
				else if (n > target)
				{
					int t = right - 1;
					while (t > left && nums[t] == nums[right])
						t--;
					right = t;
				}
				else
				{
					int t = left + 1;
					while (t < right && nums[t] == nums[left])
						t++;
					left = t;
				}
			}
			int t = cur + 1;
			while (t < nums.size() && nums[t] == nums[cur])
				t++;
			cur = t;
		}
		return closest;
	}
};