3Sum Closest Problem Solution

3Sum Closest Problem: 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 :

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).

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;
}