3Sum Closest — LeetCode #16

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

Solutions:

Python

class Solution:
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()  # Sort the array
        closest_sum = float('inf')  # Initialize closest_sum to a large value
        for i in range(len(nums)):
            left = i + 1  # Left pointer
            right = len(nums) - 1  # Right pointer
            while left < right:
                curr_sum = nums[i] + nums[left] + nums[right]
                if abs(curr_sum - target) < abs(closest_sum - target):  # Update closest_sum if necessary
                    closest_sum = curr_sum
                if curr_sum < target:  # Move left pointer
                    left += 1
                elif curr_sum > target:  # Move right pointer
                    right -= 1
                else:  # Return target if we find a combination that sums to it
                    return target
        return closest_sum

C#

public class Solution {
    public int ThreeSumClosest(int[] nums, int target) {
        Array.Sort(nums);  // Sort the array
        int closestSum = int.MaxValue;  // Initialize closestSum to a large value
        for (int i = 0; i < nums.Length; i++)
        {
            int left = i + 1;  // Left pointer
            int right = nums.Length - 1;  // Right pointer
            while (left < right)
            {
                int currSum = nums[i] + nums[left] + nums[right];
                if (Math.Abs(currSum - target) < Math.Abs(closestSum - target))  // Update closestSum if necessary
                {
                    closestSum = currSum;
                }
                if (currSum < target)  // Move left pointer
                {
                    left++;
                }
                else if (currSum > target)  // Move right pointer
                {
                    right--;
                }
                else  // Return target if we find a combination that sums to it
                {
                    return target;
                }
            }
        }
        return closestSum;
    }
}

Java

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        Arrays.sort(nums);  // Sort the array
        int closestSum = Integer.MAX_VALUE;  // Initialize closestSum to a large value
        for (int i = 0; i < nums.length; i++)
        {
            int left = i + 1;  // Left pointer
            int right = nums.length - 1;  // Right pointer
            while (left < right)
            {
                int currSum = nums[i] + nums[left] + nums[right];
                if (Math.abs(currSum - target) < Math.abs(closestSum - target))  // Update closestSum if necessary
                {
                    closestSum = currSum;
                }
                if (currSum < target)  // Move left pointer
                {
                    left++;
                }
                else if (currSum > target)  // Move right pointer
                {
                    right--;
                }
                else  // Return target if we find a combination that sums to it
                {
                    return target;
                }
            }
        }
        return closestSum;
    }
}

Javascript

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number}
 */
var threeSumClosest = function(nums, target) {
    nums.sort((a, b) => a - b);  // Sort the array
    let closestSum = Number.MAX_VALUE;  // Initialize closestSum to a large value
    for (let i = 0; i < nums.length; i++) {
        let left = i + 1;  // Left pointer
        let right = nums.length - 1;  // Right pointer
        while (left < right) {
        let currSum = nums[i] + nums[left] + nums[right];
        if (Math.abs(currSum - target) < Math.abs(closestSum - target)) {  // Update closestSum if necessary
            closestSum = currSum;
        }
        if (currSum < target) {  // Move left pointer
            left++;
        } else if (currSum > target) {  // Move right pointer
            right--;
        } else {  // Return target if we find a combination that sums to it
            return target;
        }
        }
    }
    return closestSum;
};

Typescript

function threeSumClosest(nums: number[], target: number): number {
    nums.sort((a, b) => a - b);  // Sort the array
    let closestSum = Number.MAX_VALUE;  // Initialize closestSum to a large value
    for (let i = 0; i < nums.length; i++) {
        let left = i + 1;  // Left pointer
        let right = nums.length - 1;  // Right pointer
        while (left < right) {
        let currSum = nums[i] + nums[left] + nums[right];
        if (Math.abs(currSum - target) < Math.abs(closestSum - target)) {  // Update closestSum if necessary
            closestSum = currSum;
        }
        if (currSum < target) {  // Move left pointer
            left++;
        } else if (currSum > target) {  // Move right pointer
            right--;
        } else {  // Return target if we find a combination that sums to it
            return target;
        }
        }
    }
    return closestSum;
};

PHP

class Solution {

    /**
     * @param Integer[] $nums
     * @param Integer $target
     * @return Integer
     */
    function threeSumClosest($nums, $target) {
        sort($nums);  // Sort the array
        $closestSum = PHP_INT_MAX;  // Initialize closestSum to a large value
        for ($i = 0; $i < count($nums); $i++) {
            $left = $i + 1;  // Left pointer
            $right = count($nums) - 1;  // Right pointer
            while ($left < $right) {
            $currSum = $nums[$i] + $nums[$left] + $nums[$right];
            if (abs($currSum - $target) < abs($closestSum - $target)) {  // Update closestSum if necessary
                $closestSum = $currSum;
            }
            if ($currSum < $target) {  // Move left pointer
                $left++;
            } else if ($currSum > $target) {  // Move right pointer
                $right--;
            } else {  // Return target if we find a combination that sums to it
                return $target;
            }
            }
        }
        return $closestSum;
    }
}

I hope this helps! Let me know if you have any questions. Don’t forget to follow and give some claps and comments