```
class Solution:
"""
the basic idea is 1, sort the input list
2. change the problem to twoSumCloset
"""
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
numbers = nums
if len(numbers) < 3:
return
numbers.sort() # very important for latter action
result = sys.maxsize
minDiff = sys.maxsize
#loop the sorted numbers
for idx, num in enumerate(numbers):
t = target - num
#go to twoSum problem
curDiff, twoSumResults = self.twoSumCloset(numbers[idx+1:], t)
if minDiff > curDiff:
minDiff = curDiff
result = num + numbers[idx+1+twoSumResults[0]] + numbers[idx+1+twoSumResults[1]]
return result
def twoSumCloset(self, numbers, target):
idx1 = None
idx2 = None
minDiff = sys.maxsize
start, end =0, len(numbers)-1
# loop: change the sum by moving from the left(+1) or right(-1)
# make use of the sorted numbers
while start < end:
curSum = numbers[start] + numbers[end]
curDiff = abs(curSum-target)
if curDiff < minDiff:
minDiff = curDiff
idx1 = start
idx2 = end
if curSum < target:
start += 1
elif curSum > target:
end -=1
else: # it means curSum=target!!!
break
return minDiff, [idx1, idx2]
```