16-最接近的三数之和

import java.util.Arrays;

/**
最接近的三数之和:16
2026-10-07 12:52:12
//给定一个长度为 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
//解释：与 target 最接近的和是 0（0 + 0 + 0 = 0）。 
//
// 
//
// 提示： 
//
// 
// 3 <= nums.length <= 1000 
// -1000 <= nums[i] <= 1000 
// -10⁴ <= target <= 10⁴ 
// 
//
// Related Topics 数组 双指针 排序 👍 1826 👎 0

**/

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    /**
     * 思路：先排序，先确定外层循环， 然后内层循环用双指针。 双指针通过排序后， 大于target， 则right--， 小于target，则left++
     *
     * 答成功:
     *  执行耗时:16 ms,击败了66.04% 的Java用户
     *  内存消耗:44.7 MB,击败了68.74% 的Java用户
     *  
     *  时间复杂度度 O（N^2)
     *  空间复杂度 O(1)
     * @param nums
     * @param target
     * @return
     */
    public int threeSumClosest(int[] nums, int target) {
        if(nums  == null || nums.length == 0 || nums.length < 3) {
            return 0;
        }
        Arrays.sort(nums);
        int min = nums[0] + nums[1] + nums[2];
        for(int i=0; i < nums.length; i ++) {
            int left = i + 1;
            int right = nums.length - 1;
            while (left < right && left < nums.length && right > i) {
               int sum = nums[i] + nums[left] + nums[right];
               if(Math.abs(sum - target) < Math.abs(min - target)) {
                   min = sum;
               }
               if(sum > target) {
                   right --;
               } else if(sum < target)  {
                   left ++;
               } else  {
                   return target;
               }

            }
        }
        return min;

    }
}
//leetcode submit region end(Prohibit modification and deletion)