noodleProblems/
3Sum Closest
#26

3Sum Closest

AlgorithmmediumArrayTwo PointersSorting

Given an integer array nums of length at least 3 and an integer target, pick exactly three distinct elements whose sum is as close to target as possible.

Return that closest sum. The input is guaranteed to have exactly one such closest sum.

Example cases

  • basic
    in nums = [-1,2,1,-4], target = 1
    out 2
    The closest sum is (-1) + 2 + 1 = 2, which is 1 away from the target.
  • all same
    in nums = [0,0,0], target = 1
    out 0
    The only triple sums to 0.
  • exact hit
    in nums = [1,1,1,0], target = -100
    out 2
    The smallest possible triple sum, 1 + 1 + 0 = 2, is the closest you can get to -100.

Constraints

  • 3 <= nums.length <= 500
  • -1000 <= nums[i] <= 1000
  • -10^4 <= target <= 10^4
  • Exactly one closest sum exists.
Saved
nums =
[-1,2,1,-4]
target =
1