题目

给你一个长度为 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

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -10^4 <= target <= 10^4

解题方法

双指针法

枚举所有情况需要三重循环，时间复杂度为O(n^3)。
由于乱序情况下遍历数组无法优化，因此先排序，耗时O(nlogn)。
排序后枚举第一个元素，其余两个通过双指针进行查找
当sum(*i, *left, *right)<target时，left++。
当sum(*i, *left, *right)>target时，right--。
相等时直接返回。
时间复杂度O(n^2)

c++代码

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        int out = INT_MAX/2;
        for(int i = 0; i<n-2; i++) {
            while(i>0 && nums[i] == nums[i-1] && i<n-2) ++i;
            int left = i+1;
            int right = n-1;
            while(left<right) {
                int sum = nums[i]+nums[left]+nums[right];
                if (abs(sum-target)<abs(out-target))    out = sum;
                if (sum == target)  return sum;
                if (sum<target) {
                    left++;
                    while (left>i+1 && nums[left] == nums[left-1] && left<right)  ++left;
                }
                if (sum>target) {
                    right--;
                    while (right<n-1 && nums[right] == nums[right+1] && left<right)  --right;
                }
            }
        }
        return out;
    }
};