128 - 16 最接近的三数之和

题目

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

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

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

解答

感觉就是，排序，双指针，然后记录一下与目标绝对值差距最小的答案。

https://leetcode-cn.com/problems/3sum-closest/solution/hua-jie-suan-fa-16-zui-jie-jin-de-san-shu-zhi-he-b/

var threeSumClosest = function(nums, target) {
  nums.sort((a, b) => a - b)
  let ans = nums[0] + nums[1] + nums[2]
  for (let i = 0; i < nums.length - 2; i++) {
    let start = i + 1,
      end = nums.length - 1
    while (start < end) {
      const sum = nums[start] + nums[end] + nums[i]
      if (Math.abs(sum - target) < Math.abs(ans - target)) {
        ans = sum
      }
      if (target > sum) {
        start++
      } else if (target < sum) {
        end--
      } else {
        return ans
      }
    }
  }
  return ans
};

Runtime: 68 ms, faster than 67.42% of JavaScript online submissions for 3Sum Closest.

Memory Usage: 35.1 MB, less than 100.00% of JavaScript online submissions for 3Sum Closest.

https://leetcode-cn.com/problems/3sum-closest/solution/dui-shuang-zhi-zhen-fa-jin-xing-yi-dian-you-hua-da/

根据这个优化，前两个还可以，最后一个总感觉没那么巧。。

但总感觉，这都是小概率事件。。

var threeSumClosest = function(nums, target) {
  nums.sort((a, b) => a - b)
  let ans = nums[0] + nums[1] + nums[2]
  for (let i = 0; i < nums.length - 2; i++) {
    let start = i + 1,
      end = nums.length - 1
    const min = nums[i] + nums[start] + nums[start + 1]
    const max = nums[i] + nums[end] + nums[end - 1]
    if (target < min) {
      if (Math.abs(min - target) < Math.abs(ans - target)) {
        ans = min
        continue
      }
    }
    if (target > max) {
      if (Math.abs(max - target) < Math.abs(ans - target)) {
        ans = max
        continue
      }
    }
    while (start < end) {
      const sum = nums[start] + nums[end] + nums[i]
      if (Math.abs(sum - target) < Math.abs(ans - target)) {
        ans = sum
      }
      if (target > sum) {
        start++
        while (nums[start] === nums[start - 1]) {
          start++
        }
      } else if (target < sum) {
        end--
        while (nums[end] === nums[end + 1]) {
          end--
        }
      } else {
        return ans
      }
    }
    while (nums[i] === nums[i + 1]) {
      i++
    }
  }
  return ans
};

Runtime: 48 ms, faster than 100.00% of JavaScript online submissions for 3Sum Closest.

Memory Usage: 35.7 MB, less than 100.00% of JavaScript online submissions for 3Sum Closest.

func abs(a int) int {
    if a < 0 {
        return -a
    }
    return a
}
func threeSumClosest(nums []int, target int) int {
    sort.Ints(nums)
    ans := nums[0] + nums[1] + nums[2]
    for i := 0; i < len(nums)-2; i++ {
        start := i + 1
        end := len(nums) - 1
        for start < end {
            sum := nums[start] + nums[end] + nums[i]
            if abs(sum-target) < abs(ans-target) {
                ans = sum
            }
            if target > sum {
                start++
            } else if target < sum {
                end--
            } else {
                return ans
            }
        }
    }
    return ans
}

Runtime: 4 ms, faster than 95.54% of Go online submissions for 3Sum Closest.

Memory Usage: 2.7 MB, less than 66.67% of Go online submissions for 3Sum Closest.

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        ans = nums[0]+nums[1]+nums[2]
        for i in range(len(nums)-2):
            start = i+1
            end = len(nums)-1
            while start < end:
                _sum = nums[start]+nums[end]+nums[i]
                if abs(_sum-target) < abs(ans - target):
                    ans = _sum
                if target > _sum:
                    start += 1
                elif target < _sum:
                    end -= 1
                else:
                    return ans
        return ans

Runtime: 144 ms, faster than 52.05% of Python3 online submissions for 3Sum Closest.

Memory Usage: 13.7 MB, less than 5.41% of Python3 online submissions for 3Sum Closest.