16. 3Sum Closest

题目链接

https://leetcode.com/problems/3sum-closest/

解题思路

思路和15. 3Sum类似。
题目求a + b + c 的和尽可能等于 target，，同样可以按照 a <= b <= c来满足题意，所以需要对数组从小到大排序，这样就可以先确定a，确定a之后，用a - target，在a - target的右边找b和c即可，使得b + c 尽可能接近（target - a）。

代码

class Solution {

public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ans = target, mi = 0x3fffffff;
        sort(nums.begin(), nums.end());
        for (int i = 0; i < nums.size() - 2; ++i) {
            if (i > 0 && nums[i] == nums[i - 1]) {//a和前一个数相等，也不再找
                continue;
            }
            int a = nums[i] - target;

            int st = i + 1, ed = nums.size() - 1, t = -a;
            while (st < ed) {
                //nums[st]就是b，nums[ed]就是c。
                int add = nums[st] + nums[ed];
                int dif = t - add;
                if (dif == 0) {
                    return target;
                } else if (dif > 0) {//b+c<-a，b往后移
                    if (dif < mi) {
                        mi = dif;
                        ans = nums[i] + add;
                    }
                    st++;
                } else {//b+c>-a，c往前移
                    if (-dif < mi) {
                        mi = -dif;
                        ans = nums[i] + add;
                    }
                    ed--;
                }
            }

        }
        return ans;
    }
};