leetcode16 最接近的三数之和——相向双指针

---

一、题目描述

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

链接：https://leetcode-cn.com/problems/3sum-closest

二、解题思路与代码

1.暴力解法是最容易想到的。本题求与目标数最接近的三数之和，利用三重循环即可解题。发现题目数组长度范围为
3 <= nums.length <= 1000，O(N3)为10^9，超过测评机每秒运行次数，测评机每秒运行次数在10 ^8左右。因此暴力解法不可行。
2.采用双指针。固定第一个数，然后相向双指针遍历后面的数，使总体时间复杂度下降到O(N2)。双指针一般可以将时间复杂度降低一个量级。本题使用双指针需保证数组有序，否则无法发挥其能力。使用Arrays.sort()，时间复杂度为O(log2N)，因此整体时间复杂度为O(N2).
1和2方法都需要使用一个全局变量来保存最接近target的三数之和。

public int threeSumClosest(int[] nums, int target) {
     if (nums == null || nums.length < 3) {
         return Integer.MIN_VALUE;
     }
     Arrays.sort(nums);

     int best = 10000; // 不使用Integer.MAX_VALUE 是为了避免溢出上限导致不符预期
     
     for (int fir = 0; fir < nums.length - 2; fir++) {
         int sec = fir + 1;
         int third = nums.length - 1;
         
         while (sec < third) {
             
             int sum = nums[fir] + nums[sec] + nums[third];
             if (sum == target) {
                 return target;
             }

             if (Math.abs(sum - target) < Math.abs(best - target)) {
                 best = sum;
             }


             if (sum < target) {
                 sec++;
             } else {
                 third--;
             }

         }
     }
     return best;
}

---

三、注意事项

1.使用Integer.MIN_VALUE、Integer.MAX_VALUE等时 需要考虑潜在的溢出边界值情形。
2.有可以优化的地方，sec和third指针移动时 可以与前时刻位置数比较，若相等则可以继续移动，跳过此次计算。