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).
Table of Contents
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;
}