Find the triple whose sum is nearest to a given target.
Write a function `three_sum_closest(nums: List[int], target: int) -> int` that takes a list of integers `nums` (length at least 3) and a target integer, and returns the sum of any three numbers in `nums` that is closest to the target. If multiple sums are equally close (same absolute difference from target), return the smallest such sum. The input list is not necessarily sorted.
For example, given `nums = [10, 20, 30, 40, 50]` and `target = 100`, the possible sums of triples include `10+20+30=60` (distance 40), `10+20+40=70` (distance 30), `10+20+50=80` (distance 20), `10+30+40=80` (distance 20), `10+30+50=90` (distance 10), `10+40+50=100` (distance 0), `20+30+40=90` (distance 10), `20+30+50=100` (distance 0), `20+40+50=110` (distance 10), `30+40+50=120` (distance 20). The closest distance is 0 (sums 100 and 100), so the answer is `100`. For `nums = [-1, 2, 1, -4]` and `target = 1`, the closest sum is `2` (distance 1).
Your solution must be efficient: do not enumerate all triples (O(n^3) is too slow). Use sorting and a two-pointer technique to achieve O(n^2) time.
The function signature is:
```python
def three_sum_closest(nums: List[int], target: int) -> int:
```
You need to import `List` from typing if you use type hints.
Return the integer sum, not the triple itself.
Constraints
- 3 <= len(nums) <= 10^4
- -10^9 <= nums[i] <= 10^9
- -10^9 <= target <= 10^9
- The solution must run in O(n^2) time and O(1) extra space (beyond sorting).
Example
>>> three_sum_closest([-1, 2, 1, -4], 1)
2
>>> three_sum_closest([0, 0, 0], 1)
0
>>> three_sum_closest([1, 1, 1, 0], -100)
2
>>> three_sum_closest([1, 2, 3, 4], 5)
6
>>> three_sum_closest([10, 20, 30, 40, 50], 100)
100
20 points
~20 min