image.png

思路：

双指针（步骤如↓↓↓）

  1. 排序 *（降序）
  2. 固定一个数n1（从第一个数开始），然后在数组头部找到n2 (left指针)，在数组尾部找到n3（right指针）
  3. sum=n1+n2+n3,为了靠近target（开始循环），如果：

sum > target，说明sum应该更小一点，left指针就应该往后走。
sum < target，说明sum应该更大一点，right指针就应该往前走。

  1. |sum-target| 越小，说明越接近target。找到最小值，并返回当前sum，完毕！
    1. let nums = [-1,2,1,-4], target = 1
    2.      var threeSumClosest = function (nums, target) {
    3.          nums = nums.sort((a, b) => b - a)
    4.          let near = Infinity
    5.          let res
    6.          for (let i = 0; i < nums.length - 2; i++) {
    7.              let norm = i, left = norm + 1, right = nums.length - 1
    8.              while (left < right) {
    9.                  let sum = nums[norm] + nums[left] + nums[right]
    10.                  let abs = Math.abs(target - sum)
    11.                  if (abs < near) {
    12.                      near = abs;
    13.                      res = sum;
    14.                  }
    15.                  if (sum > target) {
    16.                      left++;
    17.                  } else {
    18.                      right--;
    19.                  }
    20.              }
    21.          }
    22.          return res
    23.      };
    24.      console.log(threeSumClosest(nums, target));
    时间复杂度：O(n^2)
    空间复杂度：O(n)