Python 52ms (100%) with explanation

• The solution is not very elegantly written but it does the jobs. I just want to point out few lines (marked with "### see this ###" in the code below) that improves the speed further, compared to brute force O(N^2) answers.

The steps:
(0) if the target is <=0, sort the array, otherwise I sort the array reversely so it's from large to small.
(1) for 3 numbers with index i,j,k, I loop i through 0, 1, 2.. len(nums)
(2) then loop j from i+1, i+2.., meanwhile loop k through len(nums)-1, len(nums)-2.. until j==k
(3) break the i loop once nums[i] > 0 (in the case of target > 0, nums[i] <0), since at this point, all 3 numbers will be positive and can no longer return any sum that's smaller than previously obtained smallest (since they have negative numbers plus all the positive number you have now).

``````class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
if target <= 0:### see this ###
out = abs(sum(nums[:3])-target)
out_sum = sum(nums[:3])
n=len(nums)
for i in xrange(n):
j,k=i+1,n-1
while j<k:
isum=nums[i]+nums[j]+nums[k]
if abs(isum-target) < out:
out = abs(isum-target)
out_sum = isum
if isum > target:
k-=1
elif isum < target:
j+=1
elif isum==target:
return isum
if nums[i]>0:### see this ###
return out_sum
return out_sum
if target > 0:  ### see this ###
nums = nums[::-1]### see this ###
out = abs(sum(nums[:3])-target)
out_sum = sum(nums[:3])
n=len(nums)
for i in xrange(n):
j,k=i+1,n-1
while j<k:
isum=nums[i]+nums[j]+nums[k]
if abs(isum-target) < out:
out = abs(isum-target)
out_sum = isum
if isum < target:
k-=1
elif isum > target:
j+=1
elif isum==target:
return isum
if nums[i]<0:### see this ###
return out_sum
return out_sum
``````

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