16. 3Sum Closest
You get an integer array nums (at least three elements) and an integer target. Pick three different positions in the array and add up their values. Out of every possible choice, return the sum that lands closest to target — the one whose absolute distance |sum − target| is smallest.
If two achievable sums are equally close (one below the target and one above), return the smaller of the two.
You return the sum itself, not the indices. An exact hit is possible: if some triple sums to target exactly, that is the answer.
Example 1:
Input: nums = [4, -1, 2, 10], target = 6
Output: 5
Explanation: The four possible triples sum to 5, 13, 16, and 11. The sum 5 sits only 1 away from the target 6, so it wins.
Example 2:
Input: nums = [-2, 0, 2, 2], target = 1
Output: 0
Explanation: The achievable sums are 0, 2, and 4. Both 0 and 2 are exactly 1 away from the target, so the tie goes to the smaller sum, 0.
Constraints:
- 3 ≤ nums.length ≤ 500
- -1000 ≤ nums[i] ≤ 1000
- -10⁴ ≤ target ≤ 10⁴
- If two sums are equally close to target, the smaller sum is the answer.
Hints:
Trying all triples works: track the sum with the smallest |sum − target| seen so far (preferring the smaller sum on ties). That is O(n³) — can you cut a factor of n?
Sort the array first. With nums sorted, fix the smallest element of the triple and hunt for the other two with a left/right pointer pair.
For a fixed first element, if the current three-sum is below target, only moving the left pointer right can bring it closer from below; if above, move the right pointer left. Record every candidate against the best so far and stop early on an exact hit.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums = [4, -1, 2, 10], target = 6
Expected output: 5