求解：找出与给定目标值最接近的三数之和

嘿，你的思路方向完全没问题！咱们可以把这个想法落地成更具体、高效的实现方案，步骤如下：

核心思路拆解 #

• 先排序数组：排序是为了后续用双指针法快速缩小搜索范围，避免不必要的重复计算，整体时间复杂度主要由遍历+双指针的O(n²)主导（排序仅为O(n log n)，可以忽略）。
• 遍历每个元素作为第一个数：对于数组中的每个元素number_1，我们把问题转化为在剩下的元素中找两个数，使得它们的和最接近target - number_1。
• 双指针搜索另外两个数：在当前number_1之后的子数组里，用左指针left（初始为当前索引+1）和右指针right（初始为数组末尾），计算这三个数的总和current_sum = number_1 + nums[left] + nums[right]：
  • 如果current_sum等于target，直接返回target（这是最完美的情况，没有比它更接近的了）
  • 如果current_sum比target小，说明需要更大的数，把left右移
  • 如果current_sum比target大，说明需要更小的数，把right左移
  • 每次计算current_sum和target的差值绝对值，和当前记录的最小差值比较，更新最接近的和

示例演示 #

拿题目里的例子来说：

给定数组S = {-1, 2, 1, -4}，目标值target = 1

1. 先排序数组：[-4, -1, 1, 2]
2. 遍历第一个元素-4，目标变为1 - (-4) = 5，在[-1,1,2]里找两个数和最接近5，此时双指针得到的和是1+2=3，总和是-4+3=-1，和target的差值是2
3. 遍历第二个元素-1，目标变为1 - (-1) = 2，在[1,2]里找两个数，和是3，总和是-1+3=2，差值是0（这是目前最小的）
4. 后续遍历剩下的元素，不会得到比2更接近1的和，所以最终返回2

代码实现（Python） #

def threeSumClosest(nums, target):
    nums.sort()
    n = len(nums)
    closest_sum = nums[0] + nums[1] + nums[2]  # 初始化最接近的和
    
    for i in range(n - 2):
        left = i + 1
        right = n - 1
        current_target = target - nums[i]
        
        while left < right:
            two_sum = nums[left] + nums[right]
            current_sum = nums[i] + two_sum
            
            # 如果找到完全匹配的，直接返回
            if current_sum == target:
                return target
            
            # 更新最接近的和
            if abs(current_sum - target) < abs(closest_sum - target):
                closest_sum = current_sum
            
            # 移动指针调整和的大小
            if two_sum < current_target:
                left += 1
            else:
                right -= 1
    
    return closest_sum

这个方案的时间复杂度是O(n²)，空间复杂度取决于排序的实现（Python的sort是Timsort，空间复杂度O(n)），在大多数场景下都足够高效。

内容的提问来源于stack exchange，提问作者mourinho