分析

• 本题的考点：双指针。

• 本题的暴力解法是三种循环枚举三个数，时间复杂度是$O(n^3)$的，不可取。

• 为了使用双指针，首先对数组进行排序，然后我们可以用i枚举三个数中的其中一个，然后使用双指针j、k找到另外两个数。这里假设i < j < k。

• 对于当前考虑的nums[i]，此时可以看成定值，我们初始化j = i+1, k = nums.size()-1，对于nums[j]来说，我们需要找到一个最小的k，使得有$nums[i]+nums[j]+nums[k]\ge target$；因为k是最小的一个，所以一定有$nums[i]+nums[j]+nums[k-1] < target$。这样最接近target的两种情况都能枚举到。

• 则当j增大时，k必须减小，否则两者都增大的话，三者之和会增大，而我们要找到三者之和为0的数据，不符合要求。这类似于对撞指针。

• 因为我们要存储当前三数之和与target的差值以及三数之和，因此可以使用pair。

代码

• C++

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {

        sort(nums.begin(), nums.end());

        pair<int, int> res(INT_MAX, INT_MAX);  // (三数之和与target的差值的绝对值, 三数之和)
        for (int i = 0; i < nums.size(); i++) 
            for (int j = i + 1, k = nums.size() - 1; j < k; j++) {
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) k--;
                int s = nums[i] + nums[j] + nums[k];
                res = min(res, make_pair(abs(s - target), s));
                if (j < k - 1) {
                    s = nums[i] + nums[j] + nums[k - 1];
                    res = min(res, make_pair(abs(s - target), s));
                }
            }
        return res.second;
    }
};

• Java

class Solution {
    static class MyPair {
        int x, y;
        public MyPair(int x, int y) {
            this.x = x; this.y = y;
        }
    }

    public int threeSumClosest(int[] nums, int target) {

        Arrays.sort(nums);

        MyPair res = new MyPair(Integer.MAX_VALUE, Integer.MAX_VALUE);
        for (int i = 0; i < nums.length; i++) 
            for (int j = i + 1, k = nums.length - 1; j < k; j++) {
                while (j < k - 1 && nums[i] + nums[j] + nums[k - 1] >= target) k--;
                int s = nums[i] + nums[j] + nums[k];
                if (Math.abs(s - target) < res.x) {
                    res.x = Math.abs(s - target);
                    res.y = s;
                }
                if (j < k - 1) {
                    s = nums[i] + nums[j] + nums[k - 1];
                    if (Math.abs(s - target) < res.x) {
                        res.x = Math.abs(s - target);
                        res.y = s;
                    }
                }
            }
        return res.y;
    }
}

时空复杂度分析

• 时间复杂度：$O(n^2)$，n为数组长度。因为外层循环中每次循环都会执行一次双指针算法，双指针算法时间复杂度是$O(n)$的，因此总体时间复杂度为$O(n^2)$的。

• 空间复杂度：$O(1)$。