LeetCode 16.最接近的三数之和

给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。

返回这三个数的和。

假定每组输入只存在恰好一个解。

示例 1：

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2)。
示例 2：

输入：nums = [0,0,0], target = 1
输出：0
解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。

提示：

3 <= nums.length <= 1000
-1000 <= nums[i] <= 1000
-10${}^4$ <= target <= 10${}^4$

先对nums进行排序，然后固定一个数字，相向双指针找出最接近的三数之和：

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

        int sum = numeric_limits<int>::max() - 1e4;

        for (int i = 0; i < nums.size() - 2; ++i) {
            int left = i + 1;
            int right = nums.size() - 1;

            // 优化，如果当前固定的数字与其右边最小的两个数字之和curMinSum已经大于target
            // 那么剩余的所有数字中，任意三数之和都大于等于curMinSum
            int curMinSum = nums[i] + nums[left] + nums[left + 1];
            if (curMinSum > target) {
                if (abs(curMinSum - target) < abs(sum - target)) {
                    sum = curMinSum;
                }
                break;
            }

            // 优化，如果当前固定的数字与其右边最大的两个数字之和curMaxSum还是小于target
            // 那么当前固定的数字与其右边所有数字之和都小于curMaxSum
            // 此时只用检查当前固定的数字和其右边最大的两个数字之和即可
            int curMaxSum = nums[i] + nums[right] + nums[right - 1];
            if (curMaxSum < target) {
                if (abs(curMaxSum - target) < abs(sum - target)) {
                    sum = curMaxSum;
                }
                continue;
            }

            while (left < right) {
                int s = nums[left] + nums[right] + nums[i];

                if (abs(s - target) < abs(sum - target)) {
                    sum = s;
                }

                if (s < target) {
                    ++left;
                } else if (s > target) {
                    --right;
                } else {
                    return s;
                }
            }
        }

        return sum;
    }
};

如果nums的长度为n，则此算法时间复杂度为O(n${}^2$)，空间复杂度为O(logn)。