Two Pointers Pointers from both ends
159. 3Sum Closest
You are given an array of integers nums and an integer target. Pick three elements at three different
positions and add them up. Return the sum that is closest to target.
The distance of a sum from target is the absolute value of their difference. If two different sums are
equally close, one below target and one above it, return the smaller sum.
Example 1
Input: nums = [-4, 9, 1, -7, 5, 3], target = 12
13Explanation: No three elements add up to exactly 12. The sum 9 + 1 + 3 = 13 is 1 away, and no other sum is as close.
Example 2
Input: nums = [9, 1, 5, 2], target = 10
8Explanation: The four possible sums are 15, 12, 16 and 8. Both 8 and 12 are 2 away from 10, so we return the smaller one, 8.
Example 3
Input: nums = [1000000000, 1000000000, 1000000000]
target = -1000000000
3000000000Explanation: There is only one triple. Its sum, 3000000000, is too large for a 32-bit integer, and it is 4000000000 away from the target.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
3 ≤ nums.length ≤ 3000-109 ≤ nums[i] ≤ 109-109 ≤ target ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.