In this Leetcode 3Sum Closest problem solution we have given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to the target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

Leetcode 3Sum Closest problem solution


Problem solution in Python.

class Solution:
    def helper(self, nums, left, target, curr, res):
        right = len(nums)-1

        while left<right:
            curr_sum = curr+nums[left]+nums[right]
            diff = abs(curr_sum-target)
            if diff<res[0]:
                res[0] = diff
                res[1] = curr_sum
                
            if curr_sum<target: 
                left+=1
                while left<right and nums[left]==nums[left-1]: left+=1
            elif curr_sum>target:
                right-=1
                while left<right and nums[right]==nums[right+1]: right-=1
            else:
                return
            
            
                
        
    def threeSumClosest(self, nums: List[int], target: int) -> int:
        nums.sort()
        res = [float('inf'), 0]
        
        for i in range(len(nums)):
            if i>0 and nums[i]==nums[i-1]: continue
            self.helper(nums, i+1, target, nums[i], res)
            if res[1]==target: return res[1]
        
        return res[1]



Problem solution in Java.

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int n=nums.length;
        if(n<3)
            return 0;
        Arrays.sort(nums);
        int min = Integer.MAX_VALUE;
        int res = 0;
        for(int i=0;i<n-2;i++) {
            int j=i+1;
            int k=n-1;
            while(j<k) {
                int sum = nums[i]+nums[j]+nums[k];
                int diff = Math.abs(sum-target);
                if(diff==0)
                    return sum;
                if(diff<min) {
                    min=diff;
                    res=sum;
                }
                if(sum <=target) {
                    j++;
                }else {
                    k--;
                }
            }
        }
        return res;
    }
}


Problem solution in C++.

class Solution {
public:

int threeSumClosest(vector<int>& nums, int target) {
    int n = nums.size(), result = INT_MAX, sum = 0;
    sort(begin(nums),end(nums));
    for(int i=0 ; i<n ; i++)
    {
        int a1 = i+1;
        int a2 = n-1;
        while(a1 < a2)
        {
            int ne_w = nums[i] + nums[a1] + nums[a2];
            if(abs(target - ne_w) < abs(result))
            {
                result = target - ne_w;
                sum = ne_w;
            }
            if(ne_w < target) 
                a1++;
            else 
                a2--;
        }
    }
    return sum;
}
};


Problem solution in C.

#include <stdlib.h>

static int cmp (const void *p, const void *q)
{
    return *(int*)p < *(int*)q ? -1 : 1;
}

int threeSumClosest (int *a, const int n, const int target)
{
    qsort(a, n, sizeof *a, cmp);
    int closest = a[0] + a[1] + a[2];
    for (int i = 0; i < n; ++i) {
        int l = i + 1;
        int r = n - 1;
        while (l < r) {
            const int sum = a[i] + a[l] + a[r];
            if (sum < target)
                ++l;
            else if (sum > target)
                --r;
            else // sum == target
                return target;
            if (abs(sum - target) < abs(closest - target))
                closest = sum;
        }
    }
    return closest;
}