Leetcode 7 最接近的三数之和

题目描述

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

例如，给定数组 nums = [-1，2，1，-4], 和 target = 1.

与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2).

解法

解法一（暴力解法）

思路：使用三层遍历，找到使三元素之和与目标值最接近的结果。

var threeSumClosest = function(nums, target) {
  let min_diff;
  let result;

  for (let i = 0; i < nums.length; i++) {
    const a = nums[i];

    for (let j = i + 1; j < nums.length; j++) {
      const b = nums[j];

      for (let k = j + 1; k < nums.length; k++) {
        const c = nums[k];
        
        const sum = a + b + c;
        if (min_diff == undefined ||  Math.abs(target - sum) < min_diff) {
          min_diff = Math.abs(target - sum);
          result = sum;
        }
      }
    }
  }
  
  return result;
};

解法二

思路：与求三数之和思想类似，都使用了双指针法。

1. 对元素进行排序
2. 给定3个指针 i,l,r， 遍历 i，然后在剩余的元素里，同时从 左（指针l）、右（指针r）两边搜索，找到使与目标值差值最小的组合。

var threeSumClosest = function(nums, target) {
  let result;
  let min_diff;
  // 排序
  nums.sort((a, b) => a-b);

  for (let i = 0; i < nums.length; i++) {

    // 跳过相同值
    if (i !==0 && nums[i] == nums[i - 1]) continue;

    let l = i + 1;
    let r = nums.length - 1;

    while (l < r) {
      const sum = nums[i] + nums[l] + nums[r];

      if (min_diff == null || Math.abs(target - sum) < min_diff) {
        min_diff = Math.abs(target - sum);
        result = sum;
      }

      // 若与目标值相同，则差值最小，返回结果
      if (sum === target) {
        return sum;
      // 若大于目标值，则调整右边元素，调小元素
      } else if (sum > target) {
        r--;
      // 若小于目标值，则调整左边元素，调大元素
      } else {
        l++;
      }
    } 
  }
  return result;
};

下图是两种方法的执行时间，可以看到第二种方法远远快于第一种。

执行结果

参考资料

• Leetcode - 最接近的三数之和