3SumClosest.cpp

//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).

#include<vector>
#include<algorithm>

using namespace std;


class _3SumClosest {
public:
	int threeSumClosest(vector<int>& nums, int target) {
		if (nums.size() < 3) return 0;
		int closest = nums[0] + nums[1] + nums[2];
		sort(nums.begin(), nums.end());
		for (int first = 0; first < nums.size() - 2; ++first) {
			if (first > 0 && nums[first] == nums[first - 1]) continue;
			int second = first + 1;
			int third = nums.size() - 1;
			while (second < third) {
				int curSum = nums[first] + nums[second] + nums[third];
				if (curSum == target) return curSum;
				if (abs(target - curSum)<abs(target - closest)) {
					closest = curSum;
				}
				if (curSum > target) {
					--third;
				}
				else {
					++second;
				}
			}
		}
		return closest;
	}
};