[LeetCode][python3]0016. 3Sum Closest

Start the journey
N2I -2020.03.21

  1. My first try
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
N = len(nums)
nums.sort()
res = float('inf') # sum of 3 number
for t in range(N):
i, j = t + 1, N - 1
while i < j:
_sum = nums[t] + nums[i] + nums[j]
if abs(_sum - target) < abs(res - target):
res = _sum
if _sum > target:
j -= 1
elif _sum < target:
i += 1
else:
return target
return res

Note:

  • abs(x) Absolute value of x

Explanation:

Using absolute value to determine the distance between sum and target. Return the smallest one.

2. A better solution

class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
length = len(nums)
closest = []
for i, num in enumerate(nums[0:-2]):
l,r = i+1, length-1
# different with others' solution
if num+nums[r]+nums[r-1] < target:
closest.append(num+nums[r]+nums[r-1])
elif num+nums[l]+nums[l+1] > target:
closest.append(num+nums[l]+nums[l+1])
else:
while l < r:
sum = num+nums[l]+nums[r]
closest.append(sum)
if sum < target:
l += 1
elif sum > target:
r -= 1
else:
return target
closest.sort(key=lambda x:abs(x-target))
return closest[0]

Note:

  • lambda x: somefunction(x) A small function that returns some function of the input x.

Explanation:

It reduces the searching time if num+nums[r]+nums[r-1]<target or num+nums[l]+nums[l+1]>target, and save all sum in closest and determine the shortest distance in the end.

HI I’m N2I. Now a Computer Science and Engineering Student of NCHU in Taiwan. Check out more about me in https://nzi2020.blogspot.com/