最接近的三数之和

发表于 | 阅读次数: |

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

示例

1
2
给定数组 nums = [-1, 2, 1, -4], target = 1;
与 target 最接近的三个数的和为 2. (-1 + 2 + 1 = 2)

方法一(暴力解决)
将给出的数组中的数值分别用三个一组进行相加，把所有结果进行排序，在排序后的值中依次和 target 值进行比较，看谁和 target 最接近即最终返回这个结果值。

CODE

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
function threeSumClosest(nums, target) {
  // TODO:
  const sortNumber = function(a, b) {
    return a - b;
  }
  var result = nums[0] + nums[1] + nums[2];
  var i, start, end;
  nums.sort(sortNumber);
  for (i = 0; i < nums.length; i++) {
    start = i + 1;
    end = nums.length - 1;
    while (start < end) {
      let sum = nums[i] + nums[start] + nums[end];
      if (Math.abs(result - target) > Math.abs(sum - target)) {
        result = sum;
      }
      if (sum < target) {
        start++;
      } else {
        end--;
      }
    }
  }
  return result;
}

总结
首先将原数组进行了从大到小的排序处理(这个排序很重要)，排序完之后，当三个数相加还没有目标值 target 大的时候，说明当前值不够，则移动一位进行下一次比较，否则从后向前移动一位。