3Sum Closest
Medium · two pointers
You are given a list of integers nums and an integer target. Pick three numbers from three different positions in nums and add them up. Return the sum that lies closest to target, meaning the one with the smallest absolute difference from it.
The sum itself is the answer, not the three numbers. If a sum hits target exactly, that is the answer. The input is chosen so that no two different sums tie for being the closest to target, so there is always exactly one correct answer.
Examples
Example 1
Input: nums = [3, 9, -4, 12, 6], target = 10
Output: 11
3 + -4 + 12 = 11 (and 9 + -4 + 6 = 11 too) is one away from 10. The next nearest sum, 8, is two away.
Example 2
Input: nums = [5, 5, 5, 5], target = 0
Output: 15
Every choice of three positions sums to 15, so that is the only sum and therefore the closest.
Example 3
Input: nums = [8, -3, 1, 6, -9], target = 0
Output: 0
8 + 1 + -9 = 0 hits the target exactly.
Constraints
- 3 <= len(nums) <= 200
- -10^6 <= nums[i] <= 10^6
- -10^6 <= target <= 10^6
- No two different sums of three numbers tie for being the closest to target.