问题描述 链接到标题

16.最接近的三数之和

解题思路 链接到标题

暴力解法，三重循环，时间复杂度为$\Theta(n^3)$;

注意到本题不关注数组中元素的初始索引，因此可以考虑利用双指针来降低时间复杂度: 首先将数组排序，最外层i从0遍历到nums.size() - 3，内层循环采用相向双指针l，r从两端向中间靠拢，并且要注意如何去重，(当然，此题可以不关注)。

代码 链接到标题 

class Solution {
  private:
    int mcmp(int a, int b, int target) {
        if (abs(a - target) < abs(b - target))
            return true;
        else
            return false;
    }

  public:
    int threeSumClosest(vector<int> &nums, int target) {
        int res = 0;
        std::sort(nums.begin(), nums.end());
        int sum = nums[0] + nums[1] + nums[2]; // 记录三数之和
        for (int i = 0; i < nums.size() - 2; i++) {
            // 跳过重复的
            if (i != 0 && nums[i] == nums[i - 1])
                continue;
            int l = i + 1, r = nums.size() - 1;
            while (l < r) {
                if (nums[i] + nums[l] + nums[r] == target)
                    return target;
                else if (nums[i] + nums[l] + nums[r] < target) {
                    if (mcmp(nums[i] + nums[l] + nums[r], sum, target))
                        sum = nums[i] + nums[l] + nums[r];
                    while (l < nums.size() - 2 && nums[l] == nums[l + 1])
                        l++;
                    l++;
                } else {
                    if (mcmp(nums[i] + nums[l] + nums[r], sum, target))
                        sum = nums[i] + nums[l] + nums[r];
                    while (r > 2 && nums[r] == nums[r - 1])
                        r--;
                    r--;
                }
            }
        }
        return sum;
    }
};