16. 3Sum Closest
Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
For example,
Given array S = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
Solution: Two Pointers
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums.sort()
closest_sum = float('inf')
for idx, num in enumerate(nums):
low = idx + 1
high = len(nums) - 1
while low < high:
three_sum = num + nums[low] + nums[high]
if three_sum == target:
return target
if three_sum < target:
low += 1
else:
high -= 1
if abs(target - three_sum) < abs(target - closest_sum):
closest_sum = three_sum
return closest_sum
Lessons:
- Time complexity is
- Use two pointers to traverse all possible sums to find the closest one.