# 16 - 3Sum Closest

解法一 - Two Pointer

這題跟 # 15 非常像，主要只差在需要用額外的變數來記錄目前答案跟 target 的差是多少，不斷尋找差值更小的。實作如下：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());

        // Note:
        // 1. Iterate to n-2 only
        // 2. Need to skip same element to avoid duplicate triplets
        int n = nums.size();
        int closestSum, minDiff=INT_MAX;
        for(int i=0; i<n-2; i++) {
            // skip same element to avoid duplicate triplets
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            searchPair(nums, target, i+1, nums[i], closestSum, minDiff);
        }

        return closestSum;
    }

private:
    void searchPair(vector<int>& nums, int target, int start, int first, int& closestSum, int& minDiff) {
        int l=start, r=nums.size()-1;

        while(l<r) {
            int sum = first+nums[l]+nums[r];
            if(abs(sum-target) < minDiff) {
                closestSum = sum;
                minDiff = abs(sum-target);
            }

            if(sum == target) {minDiff = 0; closestSum = target; return;}
            else if(sum > target) r--;
            else if(sum < target) l++;
        }
    }
};

如果不包成 function，可讀性好像也不錯：

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int res, minDiff = INT_MAX;
        sort(nums.begin(), nums.end());

        for(int i=0; i<nums.size(); i++) {
            int front = i+1;
            int back = nums.size()-1;

            while(front < back) {
                int sum = nums[i] + nums[front] + nums[back];
                int diff = abs(target - sum);

                if(diff < minDiff) {
                    minDiff = diff;
                    res = sum;
                }

                if(sum < target) {
                    front++;
                }
                else if(sum > target) {
                    back--;
                }
                else {
                    return target;
                }        
            }

            while(i+1<nums.size() && nums[i+1] == nums[i])
                i++;
        }

        return res;
    }    
};