16.最接近的三数之和

链接：16.最接近的三数之和
难度：Medium
标签：数组、双指针、排序
简介：给定一个包括  n 个整数的数组  nums  和 一个目标值  target。找出  nums  中的三个整数，使得它们的和与  target  最接近。返回这三个数的和。假定每组输入只存在唯一答案。

题解 1 - typescript

• 编辑时间：2020-06-10
• 执行用时：80ms
• 内存消耗：35.9MB
• 编程语言：typescript
• 解法介绍：如题 15。

function threeSumClosest(nums: number[], target: number): number {
  const len = nums.length;
  nums = nums.sort((a, b) => a - b);
  let min = Infinity;
  let minNum = 0;
  let maxI = target <= 0 ? 0 : target;
  for (let i = 0; i === 0 || nums[i] < maxI; i++) {
    let l = i + 1;
    let r = len - 1;
    while (l < r) {
      const num = nums[i] + nums[l] + nums[r];
      const comp = num - target;
      if (min > Math.abs(comp)) {
        min = Math.abs(comp);
        minNum = num;
      }
      if (comp < 0) l++;
      else if (comp > 0) r--;
      else if (comp === 0) return num;
    }
  }
  return minNum;
}

题解 2 - cpp

• 编辑时间：2023-07-10
• 执行用时：136ms
• 内存消耗：9.9MB
• 编程语言：cpp
• 解法介绍：二分。

class Solution {
public:
    int threeSumClosest(vector<int>& nums, int target) {
        nums.push_back(0x3f3f3f3f);
        nums.push_back(-0x3f3f3f3f);
        sort(nums.begin(), nums.end());
        int n = nums.size(), res = -0x3f3f3f3f;
        for (int i = 1; i + 2 < n; i++) {
            for (int j = i + 1; j + 1 < n; j++) {
                int l = j + 1, r = n, sum = nums[i] + nums[j];
                while (l < r) {
                    int m = (l + r) / 2;
                    if (nums[m] >= target - sum) r = m;
                    else l = m + 1;
                }
                if (sum + nums[l] == target) return target;
                if (nums[l] != INT_MAX && abs(target - sum - nums[l]) < abs(target - res)) {
                    res = sum + nums[l];
                }
                if (l != j + 1 && nums[l - 1] != INT_MIN && abs(target - sum - nums[l - 1]) < abs(target - res)) {
                    res = sum + nums[l - 1];
                }                
            }
        }
        return res;
    }
};