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
Top comments (0)