16. 最接近的三数之和：三指针 = 固定一个指针再双指针.md

题目简述：

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

返回这三个数的和。

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

题目链接：16. 最接近的三数之和

思路

这个问题和 15. 三数之和 很相似，只不过要求寻找的不是一组恰等于 target 的三数，而是最接近的一组三数，显然我们可以沿用与 15. 三数之和 相同的思路：排序，然后利用顺序信息，考虑三指针。

双指针寻找最接近的两数之和我们都知道怎么计算，对于这类问题呢？假设我们固定 left 指针，那么问题就变成了 mid 与 right 指针的最接近的两数之和问题，该问题可以用双指针法求解。最后，我们让 left 指针遍历 nums，就解出了最接近的三数之和，即所谓的三指针。

因此，关键是固定 left 指针！

虽然要固定 right 当然也是可以的~

但无论如何，关键是固定左指针或右指针，将问题转化为双指针问题！！！

请结合代码。

一个典型的误区是同时考虑三个指针而不是固定其中一个，这样问题会超级复杂。

代码

这里可以进行一些剪枝，例如若 left 移动后与移动前具有相同的双指针初始情况，那么就可以跳过；或是当 curDiff 为 0 时提前返回。这里就不做剪枝了，仅按最基本的原理实现代码。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);
        int minDiff = nums[0] + nums[1] + nums[2] - target;
        
        for (int left = 0; left < nums.length - 2; left++) {
            int mid = left + 1;
            int right = nums.length - 1;

            while (mid < right) {
                int curDiff = nums[left] + nums[mid] + nums[right] - target;
                minDiff = minAbsOne(minDiff, curDiff);

                if (curDiff > 0) {
                    right--;
                } else {
                    mid++;
                }
            }
        }

        return minDiff + target;
    }

    private int minAbsOne(int a, int b) {
        return Math.abs(a) < Math.abs(b) ? a : b;
    }
}