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.

分析：

会做3sum和two sum closest就会做这道题目。

解法：

class Solution {
public:    
    /**
     * @param numbers: Give an array numbers of n integer
     * @param target: An integer
     * @return: return the sum of the three integers, the sum closest target.
     */
    int threeSumClosest(vector<int> nums, int target) {
        // write your code here
        if (nums.size() < 3) {
            return 0;
        }
        sort(nums.begin(), nums.end() );
        vector<int> minDiffSumPair = {INT_MAX, 0};
        for (int i = 0; i < nums.size() - 2; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            int start = i + 1;
            int end = nums.size() - 1;
            while (start < end) {
                int sum = nums[i] + nums[start] + nums[end];
                if (sum == target) {
                    minDiffSumPair[0] = 0;
                    minDiffSumPair[1] = sum;
                    break;
                } else {
                    int diff = abs(sum - target);
                    if (diff < minDiffSumPair[0]) {
                        minDiffSumPair[0] = diff;
                        minDiffSumPair[1] = sum;
                    }
                    if (sum > target) {
                        end--;
                    } else {
                        start++;
                    }
                }
            }
        }
        return minDiffSumPair[1];
    }
};