# Python O(n^2), highly optimized, beats 95%

• Similar to 3sum but we track the closest value instead:

- Yangshun

``````class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# Time: O(n^2)
# Space: O(lgn)
nums, length, closest = sorted(nums), len(nums), float('inf')
for i in range(length - 2):
# Previous value of i has been accounted for.
if i > 0 and nums[i] == nums[i - 1]:
continue
j, k = i + 1, length - 1
while j < k:
total = nums[i] + nums[j] + nums[k]
if abs(total - target) < abs(closest - target):
closest = total
# Total exceeds target, decrement k so that total sum becomes smaller
if total > target:
# Find the next different k.
while j < k and nums[k] == nums[k - 1]:
k -= 1
k -= 1
else:
if total == target:
return target
# Find the next different j.
while j < k and nums[j] == nums[j + 1]:
j += 1
j += 1
return closest
``````

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