Leetcode - 3Sum Closest

Leetcode : 3Sum Closest

Description

Given an array nums of n integers 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
# The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

Approach

Set independent pointer i, and two dependant pointer variables left and right to calculate difference between target and sum of three pointers.

Solution (Python)

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums = sorted(nums)
        
        result = nums[0] + nums[1] + nums[len(nums) - 1]
        
        for i in range(len(nums) - 1):
            left = i + 1
            right = len(nums) - 1
            
            while left < right:
                current = nums[i] + nums[left] + nums[right]
                
                if current == target:
                    return target
                
                elif abs(target - current) < abs(target - result):
                    result = current 
                
                elif current > target:
                    right = right - 1
                    
                else:
                    left = left + 1
                    
        return result 

Result

Runtime: 136 ms
Memory Usage: 14.1 MB
Runtime Beats 52.51% of Python Submission