目录

一、问题描述

二、解题思路

三、代码

四、复杂度分析

---

一、问题描述

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

返回这三个数的和。

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

二、解题思路

• 排序数组：与三数之和的题类似，首先对数组进行排序。排序后的数组使得我们可以有效地使用双指针法来找到和最接近目标值的三元组。

• 遍历数组：遍历排序后的数组，固定一个数 nums[i]，然后通过双指针法来寻找另外两个数 nums[j] 和 nums[k] 使得三数之和最接近目标值 target。

• 双指针法：

  • 初始化两个指针：left 指向 i+1，right 指向数组末尾。
  • 计算三数之和 sum = nums[i] + nums[left] + nums[right]，并比较它与 target 的距离。如果 sum 更接近 target，就更新最接近的和。
  • 根据 sum 和 target 的大小关系来移动指针：如果 sum 小于 target，说明和太小，左指针右移；如果 sum 大于 target，说明和太大，右指针左移。
  • 每次都更新当前最接近的和，直到找到最接近 target 的三元组。

• 终止条件：遍历结束后，返回最接近的三元组的和。

三、代码

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        // 首先对数组进行排序
        Arrays.sort(nums);
        // 初始化最接近的和为一个大数
        int closestSum = nums[0] + nums[1] + nums[2];
        
        // 遍历数组，从第一个元素到倒数第三个
        for (int i = 0; i < nums.length - 2; i++) {
            // 初始化双指针
            int left = i + 1;
            int right = nums.length - 1;
            
            // 双指针法寻找和最接近 target 的三元组
            while (left < right) {
                // 计算当前三元组的和
                int sum = nums[i] + nums[left] + nums[right];
                
                // 如果找到一个更接近 target 的和，更新 closestSum
                if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
                    closestSum = sum;
                }
                
                // 根据 sum 和 target 的大小关系移动指针
                if (sum < target) {
                    left++;  // 如果当前和小于 target，左指针右移
                } else if (sum > target) {
                    right--;  // 如果当前和大于 target，右指针左移
                } else {
                    // 如果 sum 正好等于 target，直接返回该和
                    return sum;
                }
            }
        }
        
        // 返回最接近的和
        return closestSum;
    }
}

四、复杂度分析

时间复杂度：

• O(n^2)，其中 n 是数组的长度。排序操作的时间复杂度是 O(n log n)，双指针法的时间复杂度是 O(n^2)。

空间复杂度：

• O(1)，我们只使用了常量级别的额外空间。