Question

16. 最接近的三数之和

English Version

题目描述

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

返回这三个数的和。

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

 

示例 1：

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

示例 2：

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

 

提示：

• 3 <= nums.length <= 1000
• -1000 <= nums[i] <= 1000
• -104 <= target <= 104

解法

方法一：排序 + 双指针

我们将数组排序，然后遍历数组，对于每个元素 $nums[i]$，我们使用指针 $j$ 和 $k$ 分别指向 $i+1$ 和 $n-1$，计算三数之和，如果三数之和等于 $target$，则直接返回 $target$，否则根据与 $target$ 的差值更新答案。如果三数之和大于 $target$，则将 $k$ 向左移动一位，否则将 $j$ 向右移动一位。

时间复杂度 $O(n^2)$，空间复杂度 $O(\log n)$。其中 $n$ 为数组长度。

class Solution:
  def threeSumClosest(self, nums: List[int], target: int) -> int:
    nums.sort()
    n = len(nums)
    ans = inf
    for i, v in enumerate(nums):
      j, k = i + 1, n - 1
      while j < k:
        t = v + nums[j] + nums[k]
        if t == target:
          return t
        if abs(t - target) < abs(ans - target):
          ans = t
        if t > target:
          k -= 1
        else:
          j += 1
    return ans

class Solution {
  public int threeSumClosest(int[] nums, int target) {
    Arrays.sort(nums);
    int ans = 1 << 30;
    int n = nums.length;
    for (int i = 0; i < n; ++i) {
      int j = i + 1, k = n - 1;
      while (j < k) {
        int t = nums[i] + nums[j] + nums[k];
        if (t == target) {
          return t;
        }
        if (Math.abs(t - target) < Math.abs(ans - target)) {
          ans = t;
        }
        if (t > target) {
          --k;
        } else {
          ++j;
        }
      }
    }
    return ans;
  }
}

class Solution {
public:
  int threeSumClosest(vector<int>& nums, int target) {
    sort(nums.begin(), nums.end());
    int ans = 1 << 30;
    int n = nums.size();
    for (int i = 0; i < n; ++i) {
      int j = i + 1, k = n - 1;
      while (j < k) {
        int t = nums[i] + nums[j] + nums[k];
        if (t == target) return t;
        if (abs(t - target) < abs(ans - target)) ans = t;
        if (t > target)
          --k;
        else
          ++j;
      }
    }
    return ans;
  }
};

func threeSumClosest(nums []int, target int) int {
  sort.Ints(nums)
  ans := 1 << 30
  n := len(nums)
  for i, v := range nums {
    j, k := i+1, n-1
    for j < k {
      t := v + nums[j] + nums[k]
      if t == target {
        return t
      }
      if abs(t-target) < abs(ans-target) {
        ans = t
      }
      if t > target {
        k--
      } else {
        j++
      }
    }
  }
  return ans
}

func abs(x int) int {
  if x < 0 {
    return -x
  }
  return x
}

function threeSumClosest(nums: number[], target: number): number {
  nums.sort((a, b) => a - b);
  let ans: number = 1 << 30;
  const n = nums.length;
  for (let i = 0; i < n; ++i) {
    let j = i + 1;
    let k = n - 1;
    while (j < k) {
      const t: number = nums[i] + nums[j] + nums[k];
      if (t === target) {
        return t;
      }
      if (Math.abs(t - target) < Math.abs(ans - target)) {
        ans = t;
      }
      if (t > target) {
        --k;
      } else {
        ++j;
      }
    }
  }
  return ans;
}

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  nums.sort((a, b) => a - b);
  let ans = 1 << 30;
  const n = nums.length;
  for (let i = 0; i < n; ++i) {
    let j = i + 1;
    let k = n - 1;
    while (j < k) {
      const t = nums[i] + nums[j] + nums[k];
      if (t === target) {
        return t;
      }
      if (Math.abs(t - target) < Math.abs(ans - target)) {
        ans = t;
      }
      if (t > target) {
        --k;
      } else {
        ++j;
      }
    }
  }
  return ans;
};

class Solution {
  /**
   * @param int[] $nums
   * @param int $target
   * @return int
   */

  function threeSumClosest($nums, $target) {
    $n = count($nums);
    $closestSum = $nums[0] + $nums[1] + $nums[2];
    $minDiff = abs($closestSum - $target);

    sort($nums);

    for ($i = 0; $i < $n - 2; $i++) {
      $left = $i + 1;
      $right = $n - 1;

      while ($left < $right) {
        $sum = $nums[$i] + $nums[$left] + $nums[$right];
        $diff = abs($sum - $target);

        if ($diff < $minDiff) {
          $minDiff = $diff;
          $closestSum = $sum;
        } elseif ($sum < $target) {
          $left++;
        } elseif ($sum > $target) {
          $right--;
        } else {
          return $sum;
        }
      }
    }

    return $closestSum;
  }
}