013-最接近的三数之和 (3Sum Closest)

题目描述

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

返回这三个数的和。

假定每组输入只存在一个答案。

示例

输入：nums = [-1,2,1,-4], target = 1
输出：2
解释：与 target 最接近的和是 2 (-1 + 2 + 1 = 2) 。

输入：nums = [0,0,0], target = 1
输出：0

解题思路

先对数组进行排序，然后使用三重循环的优化版本。固定第一个数，使用双指针寻找剩余两个数，记录与目标值最接近的和。

JavaScript 解决方案

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
const threeSumClosest = (nums, target) => {
    const n = nums.length;
    
    // 如果数组长度小于3，返回前三个数的和
    if (n < 3) return nums.reduce((sum, num) => sum + num, 0);
    
    // 对数组进行排序
    nums.sort((a, b) => a - b);
    
    let closestSum = nums[0] + nums[1] + nums[2];
    let minDiff = Math.abs(closestSum - target);
    
    for (let i = 0; i < n - 2; i++) {
        // 跳过重复的第一个数
        if (i > 0 && nums[i] === nums[i - 1]) continue;
        
        let left = i + 1;
        let right = n - 1;
        
        while (left < right) {
            const sum = nums[i] + nums[left] + nums[right];
            const diff = Math.abs(sum - target);
            
            // 如果找到更接近的和，更新结果
            if (diff < minDiff) {
                minDiff = diff;
                closestSum = sum;
            }
            
            // 如果和等于目标值，直接返回
            if (sum === target) {
                return sum;
            } else if (sum < target) {
                left++;
            } else {
                right--;
            }
        }
    }
    
    return closestSum;
};

复杂度分析

时间复杂度：O(n²)，其中 n 是数组长度
空间复杂度：O(1)，只使用了常数额外空间

测试用例

// 测试函数
const testThreeSumClosest = () => {
    const testCases = [
        {
            nums: [-1, 2, 1, -4],
            target: 1,
            expected: 2
        },
        {
            nums: [0, 0, 0],
            target: 1,
            expected: 0
        },
        {
            nums: [1, 1, 1, 0],
            target: -100,
            expected: 2
        },
        {
            nums: [1, 2, 4, 8, 16, 32, 64, 128],
            target: 82,
            expected: 82
        },
        {
            nums: [-1, 0, 1, 1, 55],
            target: 3,
            expected: 2
        },
        {
            nums: [0, 2, 1, -3],
            target: 1,
            expected: 0
        }
    ];

    testCases.forEach((testCase, index) => {
        const result = threeSumClosest(testCase.nums, testCase.target);
        const passed = result === testCase.expected;
        console.log(`测试用例 ${index + 1}: ${passed ? '通过' : '失败'}`);
        console.log(`输入: nums = [${testCase.nums}], target = ${testCase.target}`);
        console.log(`期望: ${testCase.expected}, 实际: ${result}\n`);
    });
};

// 运行测试
testThreeSumClosest();

关键点总结

排序预处理：先对数组排序，便于双指针操作
三重循环优化：固定第一个数，使用双指针寻找剩余两个数
距离计算：使用绝对值计算与目标值的距离
提前返回：如果找到等于目标值的和，直接返回
双指针技巧：根据和与目标值的大小关系移动指针

总结

这道题考察了以下重点：

双指针技巧：在排序数组中使用双指针寻找目标值
距离计算：如何计算与目标值的距离
算法优化：通过排序和剪枝提高效率
边界处理：对数组长度不足的情况的处理

排序+双指针法是最优解，时间复杂度为 O(n²)，空间复杂度为 O(1)。在实际面试中，建议先提出暴力解法，然后优化到双指针解法。

013-最接近的三数之和 (3Sum Closest)

On this page