力扣每日一题：最接近的三数之和

傷城~ 2024-03-17 20:19 41阅读 0赞

**题目：给你一个长度为 n 的整数数组 nums 和 一个目标值 target。请你从 nums 中选出三个整数，使它们的和与 target 最接近。 返回这三个数的和。 假定每组输入只存在恰好一个解。**

import java.util.Arrays;
    
    public class ThreeSumClosest {
        public int threeSumClosest(int[] nums, int target) {
            Arrays.sort(nums);
            int closestSum = nums[0] + nums[1] + nums[2]; // 初始化为前三个数的和
            int n = nums.length;
    
            for (int i = 0; i < n ; i++) {
                int left = i + 1;
                int right = n - 1;
    
                while (left < right) {
                    int sum = nums[i] + nums[left] + nums[right];
    
                    if (sum == target) {
                        return sum; // 如果找到和等于目标值的三元组，直接返回
                    }
    
                    // 更新最接近的和
                    if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
                        closestSum = sum;
                    }
    
                    if (sum < target) {
                        left++; // 和小于目标值，增大和
                    } else {
                        right--; // 和大于目标值，减小和
                    }
                }
            }
    
            return closestSum;
        }
    }

题解：与找三数和类似，同样采用双指针的方法。首先对数组进行排序，这里我进行了升序。然后将左指针指向当前元素的下一个元素，右指针指向末尾元素。

在内部循环中，先计算当前三个数的和sum，判断与target是否相等，相等则直接返回。如果不相等，更新最接近的和`closestSum`。通过比较当前和`sum`与最接近和`closestSum`与目标值`target`之间的差的绝对值大小，选择更接近的和。（Math.abs() 返回参数的绝对值。参数可以是 int, float, long, double, short, byte类型。）

根据当前和`sum`与目标值`target`的大小关系，移动左指针或右指针，以逼近目标值。如果当前和小于目标值，则增大和，移动左指针；如果当前和大于目标值，则减小和，移动右指针。

最后，返回最接近的和`closestSum`。

这种解法的时间复杂度为O(n^2)，其中n为数组的长度。