DEV Community

Abhishek Chaudhary

Posted on

3Sum Closest

Given an integer array `nums` of length `n` and an integer `target`, find three integers in `nums` such that the sum is closest to `target`.

Return the sum of the three integers.

You may assume that each input would have exactly one solution.

Example 1:

Input: nums = [-1,2,1,-4], target = 1
Output: 2
Explanation: The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Example 2:

Input: nums = [0,0,0], target = 1
Output: 0

Constraints:

• `3 <= nums.length <= 1000`
• `-1000 <= nums[i] <= 1000`
• `-104 <= target <= 104`

SOLUTION:

``````class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
n = len(nums)
if n < 3:
return []
nums = [3 * num - target for num in nums]
nums.sort()
closest = float('inf')
for i in range(n - 2):
a = nums[i]
start = i + 1
end = n - 1
while start < end:
b = nums[start]
c = nums[end]
total = a + b + c
if abs(total) < abs(closest):
closest = total
if total > 0:
end -= 1
else:
start += 1
return target + closest // 3
``````