# 3Sum Closest

• ``````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]
``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.