最接近的三数之和

题目

给定一个包括 n 个整数的数组 nums 和 一个目标值 target. 找出 nums 中的三个整数, 使得它们的和与 target 最接近. 返回这三个数的和. 假定每组输入只存在唯一答案.

提示:

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

示例

输入: nums = [-1, 2, 1, -4], target = 1

输出: 2

解释: 与 target 最接近的和是 2 (-1 + 2 + 1 = 2)

题解

首先先说一下怎么找三个数: 即固定一个数(一趟循环), 然后里面再来一次循环, 让两个指针游走, 这样来定位到三个数.

为了防止找重, 首先将数组排序, 这样的目的是找三个数

JavaScript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function (nums, target) {
  const n = nums.length
  // 先给数组排序, 便于后面使用双指针
  nums.sort((a, b) => a - b)

  // 初始化一个 ans
  let ans = nums[0] + nums[1] + nums[2]

  // 固定住 i
  for (let i = 0; i < n; i += 1) {
    // 游走 start 和 end
    let start = i + 1,
      end = n - 1

    while (start < end) {
      const sum = nums[i] + nums[start] + nums[end]

      // 说明 sum 这一组值的和更接近 target
      if (Math.abs(target - sum) < Math.abs(target - ans)) {
        ans = sum
      }

      if (sum > target) {
        end--
      } else if (sum < target) {
        start++
      } else {
        return ans
      }
    }
  }

  return ans
}

Rust

pub fn three_sum_closest(nums: Vec<i32>, target: i32) -> i32 {
    let n = nums.len();

    let mut nums = nums;
    nums.sort();

    let mut ans = nums[0] + nums[1] + nums[2];

    for i in 0..n {
        let (mut start, mut end) = (i + 1, n - 1);

        while start < end {
            let sum = nums[i] + nums[start] + nums[end];

            if (target - sum).abs() < (target - ans).abs() {
                ans = sum;
            }

            if sum < target {
                start += 1;
            } else if sum > target {
                end -= 1;
            } else {
                return ans;
            }
        }
    }

    ans
}

复杂度分析

• 时间复杂度: O(n²)

• 空间复杂度: O(1)