3Sum Closest Leetcode Solution
In this tutorial, we will solve the leetcode 3sum closest problem in python.
Task:
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
Explanation: The sum that is closest to the target is 0. (0 + 0 + 0 = 0).
Constraints:
3 <= nums.length <= 500
-1000 <= nums[i] <= 1000
-104 <= target <= 104
Solution:
class Solution:
def threeSumClosest(self, nums: List[int], target: int) -> int:
nums.sort()
min_ = 1000000
for i in range(len(nums)-2):
l = i+1
r = len(nums) - 1
while l < r:
sum_ = nums[i]+nums[l]+nums[r] - target
if abs(sum_) <= abs(min_):
min_ = sum_
if sum_ == 0:
return target
elif sum_ < 0:
l += 1
else:
r -= 1
return min_ + target
Steps:
step1: first we sort the array and set a variable named min_ to a higher integer.
step2: Now, loop through the array till it's (length - 2), and set the left and right pointers for the while loop.
step3: Now, with the while loop till l < r, we calculate the sum_ variable.
step4: Now, check the absolute of sum_ and min_ variable and if it is less than abs(min_) then we assign the min_ to sum_
step5: if sum_ is 0 then we return the target, otherwise we update the left and right pointers.
step6: After the loop we return the sum of min_ and target as our desired output.
