TNotes.leetcode

Appearance

0016. 最接近的三数之和【中等】

0016. 最接近的三数之和【中等】 ​

1. 📝 题目描述 ​

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

返回这三个数的和。

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

示例 1：

txt
输入：nums = [-1, 2, 1, -4], target = 1
输出：2

解释：与 target 最接近的和是 2 => -1 + 2 + 1 = 2。

示例 2：

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

解释：与 target 最接近的和是 0 => 0 + 0 + 0 = 0。

提示：

  • 3 <= nums.length <= 1000
  • -1000 <= nums[i] <= 1000
  • -10^4 <= target <= 10^4

2. 🎯 s.1 - 排序 + 双指针 ​

c
int compare(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int threeSumClosest(int* nums, int numsSize, int target) {
    qsort(nums, numsSize, sizeof(int), compare);
    int closest = nums[0] + nums[1] + nums[2];

    for (int i = 0; i < numsSize - 2; i++) {
        int left = i + 1, right = numsSize - 1;
        while (left < right) {
            int sum = nums[i] + nums[left] + nums[right];
            if (abs(sum - target) < abs(closest - target)) {
                closest = sum;
            }
            if (sum < target) {
                left++;
            } else if (sum > target) {
                right--;
            } else {
                return sum; // 直接等于 target，不可能更接近
            }
        }
    }
    return closest;
}
js
/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  nums.sort((a, b) => a - b)
  let closest = nums[0] + nums[1] + nums[2]

  for (let i = 0; i < nums.length - 2; i++) {
    let left = i + 1
    let right = nums.length - 1

    while (left < right) {
      const sum = nums[i] + nums[left] + nums[right]
      if (Math.abs(sum - target) < Math.abs(closest - target)) {
        closest = sum
      }
      if (sum < target) {
        left++
      } else if (sum > target) {
        right--
      } else {
        return sum // 直接等于 target，不可能更接近
      }
    }
  }
  return closest
}
py
class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        closest = nums[0] + nums[1] + nums[2]

        for i in range(len(nums) - 2):
            left, right = i + 1, len(nums) - 1
            while left < right:
                s = nums[i] + nums[left] + nums[right]
                if abs(s - target) < abs(closest - target):
                    closest = s
                if s < target:
                    left += 1
                elif s > target:
                    right -= 1
                else:
                    return s  # 直接等于 target，不可能更接近
        return closest
  • 时间复杂度：O(n2)，排序 O(nlog⁡n)，外层枚举 O(n)，内层双指针 O(n)，整体 O(n2) 主导
  • 空间复杂度：O(log⁡n)，排序递归栈空间

算法思路：

  • 先对数组升序排序，初始化最接近值 closest 为前三个数之和
  • 固定第一个数 nums[i]，左右双指针 left = i+1、right = n-1 向中收缩
    • i 指向的是三元组中最小的成员
    • left 指向的是三元组中中间的成员
    • right 指向的是三元组中最大的成员
  • 每次扫描的时候固定 i，剩余俩成员在 i 后边儿新建窗口不断收缩区间查找最优解
    • 每次指针移动，重新计算三数之和 sum，若 |sum - target| 更小则更新 closest
    • 若 sum < target 则 left++（让和变大）
    • 若 sum > target 则 right--（让和变小）
    • 若 sum == target 则直接返回

Discussions