Three Numbers Closest to a Target

Write closest_three_sum(nums, target) that picks three numbers from nums at three different positions and returns their sum, choosing the sum that is closest to target. If two different sums are equally close (one above the target and one below it), return the smaller sum.

Examples

closest_three_sum([8, -2, 5, 3, -6], 4)    # returns 5
closest_three_sum([0, 0, 0], 1)            # returns 0
closest_three_sum([1, 2, 5, 10, 11], 12)   # returns 13
closest_three_sum([1, 3, 5, 7], 12)        # returns 11

In the first example 8 + 3 + (-6) = 5 is only 1 away from 4. In the last example the sums 11 and 13 are both 1 away from 12, so the smaller sum, 11, is the answer.

Constraints

• 3 <= len(nums) <= 1,000
• -10^6 <= nums[i] <= 10^6
• -10^7 <= target <= 10^7

Note

A list of 1,000 numbers has about 166 million ways to pick three of them, too many to try one by one.