题目：https://leetcode-cn.com/problems/3sum-closest/submissions/
给定一个包括 n 个整数的数组 nums 和 一个目标值 target。找出 nums 中的三个整数，使得它们的和与 target 最接近。返回这三个数的和。假定每组输入只存在唯一答案。

我的方法一

思路和步骤和《15. 三数之和》类似，步骤可以参考https://www.jianshu.com/p/2aef26a6b0d4

优化方法

1. 参考点和左右指针，如果和上一个值一样，那么可以直接跳过

代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        int ret = target < 0 ? INT_MIN : INT_MAX;

        //O(nlogn)
        sort(nums.begin(), nums.end());

        int size = nums.size();
        int left;
        int right;
        int sum;

        //O(nxn)
        for(int i = 0; i < size; i++) {//O(n)
            //optimize 1
            if(i > 0) {
                if(nums[i] == nums[i - 1]){
                    continue;
                }
            }

            left = i + 1;
            right = size - 1;

            //O(n)
            while(left < right) {
                //optimize 2
                if(left > i + 1) {
                    if(nums[left] == nums[left - 1]){
                        left++;
                        continue;
                    }
                }
                if(right < size - 1) {
                    if(nums[right] == nums[right + 1]){
                        right--;
                        continue;
                    }
                }

                sum = nums[i] + nums[left] + nums[right];
                if(abs(sum - target) < abs(ret - target)) {
                    ret = sum;
                }

                if(sum == target) {
                    return ret;
                }else if (sum < target) {
                    left++;
                }else {
                    right--;
                }
            }
        }

        return ret;
    }
};