LeetCode 16. 最接近的三数之和（中等、数组）day13

题目描述：给你一个长度为 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

题目解析：双指针方法

本题与题目15. 三数之和非常相像，可以参考文章：https://blog.csdn.net/qq_43751200/article/details/124293990

1、首先对数据进行排序，使用Arrays.sort(nums)，时间复杂度为O(nlogn);
2、在数组nums中，进行遍历，每遍历一个值利用其下标i,形成一个固定值nums[i];
3、再使用指针left指向i的下一个位置，即left = i +1, 指针right指向数组的尾部，即right = nums.length -1;
4、根据currentSum = nums[i] + nums[left] + nums[right]的结果，判断与目标target的距离，如果更近，更新closestSum;
5、同时判断currentSum与target的大小关系，
   如果currenSum > target, right -= 1并跳过所有重复的nums[right]，
   如果currentSum < target, left+= 1并跳过所有重复的nums[left]，
   如果currentSum == target,这直接返回currentSum即可；

代码实现：

   public int threeSumClosest(int[] nums, int target) {
        // 1. 对数组进行排序
        Arrays.sort(nums);

        // 假设当前最接近target的数为前三项和
        int closestSum = nums[0] +nums[1] + nums[2];

        // 2. 遍历数组
        for(int i = 0; i < nums.length - 2; i++){
            // 2.1 定义双指针的位置信息
            int left = i + 1, right = nums.length -1;

            while (left < right){
                int currentSum = nums[i] +nums[left] +nums[right];  // 当前位置的三个数的和

                // 2.2 比较当前三个数的和到target距 与 closestSum到target的距离大小
                if(Math.abs(currentSum - target) < Math.abs(closestSum - target)){
                    closestSum = currentSum;
                }
                
                if(currentSum == target){  // 如果currentSum == target,直接返回currentSum即可
                    return currentSum;
                }else if(currentSum > target){  // 如果currenSum > target, right -= 1并跳过所有重复的nums[right]
                    while (left < right && nums[right] == nums[--right]);
                }else {  //  如果currentSum < target, left+= 1并跳过所有重复的nums[left]
                   while (left < right && nums[left] == nums[++left]);
                }
            }
        }
        return closestSum;
    }

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/3sum-closest
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。