Algorithm
Problem Name: 16. 3Sum Closest
Problem Link: https://leetcode.com/problems/3sum-closest/
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
Code Examples
#1 Code Example with C Programming
Code -
C Programming
int cmp(const void *a, const void *b) {
return *(int *)a - *(int *)b;
}
int threeSumClosest(int* nums, int numsSize, int target) {
int i, x, y, k, d, d1;
qsort(nums, numsSize, sizeof(int), cmp);
d = 0;
for (i = 0; i < numsSize - 2; i ++) {
x = i + 1;
y = numsSize - 1;
while (x < y) {
k = nums[i] + nums[x] + nums[y];
if (k == target) {
return k;
} else if (k > target) {
y --;
} else {
x ++;
}
d1 = k - target;
if (d == 0 || abs(d) > abs(d1)) {
d = d1;
}
}
}
return target + d;
}
Input
nums = [-1,2,1,-4], target = 1
Output
2
#2 Code Example with C++ Programming
Code -
C++ Programming
class Solution {
public:
int threeSumClosest(vector<int>& nums, int target) {
sort(nums.begin(), nums.end());
int diff = INT_MAX, res = 0;
for(int i = 0; i < nums.size() - 2; i++){
int lo = i + 1, hi = nums.size() - 1;
while(lo < hi){
int sum = nums[i] + nums[lo] + nums[hi];
if(sum == target) return target;
if(abs(sum - target) < diff) diff = abs(sum - target>, res = sum;
(sum > target) ? hi-- : lo++;
}
}
return res;
}
};
Input
nums = [0,0,0], target = 1
#3 Code Example with Java Programming
Code -
Java Programming
class Solution {
public int threeSumClosest(int[] nums, int target) {
Arrays.sort(nums);
int closestDiff = Integer.MAX_VALUE;
for (int i = 0; i < nums.length; i++) {
int start = i + 1;
int end = nums.length - 1;
while (start < end) {
int currSum = nums[i] + nums[start] + nums[end];
if (Math.abs(target - currSum) < Math.abs(closestDiff)) {
closestDiff = target - currSum;
}
if (currSum < target) {
start++;
} else {
end--;
}
}
}
return target - closestDiff;
}
}
Input
nums = [-1,2,1,-4], target = 1
Output
2
#4 Code Example with Javascript Programming
Code -
Javascript Programming
const threeSumClosest = function(nums, target) {
const nums = nums.sort((a, b) => a - b);
let result;
let lo;
let hi;
let sum;
result = nums[0] + nums[1] + nums[nums.length - 1];
for (let i = 0; i < nums.length - 2; i++) {
lo = i + 1;
hi = nums.length - 1;
while (lo < hi) {
sum = nums[i] + nums[lo] + nums[hi];
if (sum < target) {
while (lo < hi && nums[lo] === nums[lo + 1]) {
lo += 1;
}
lo += 1;
} else if (sum > target) {
while (lo < hi && nums[hi] === nums[hi - 1]) {
hi -= 1;
}
hi -= 1;
} else {
return sum;
}
if (Math.abs(target - sum) < Math.abs(target - result)) {
result = sum;
}
}
}
return result;
};
Input
nums = [0,0,0], target = 1
Output
09
#5 Code Example with Python Programming
Code -
Python Programming
class Solution:
def threeSumClosest(self, nums, target):
res = diff = float("inf")
nums.sort()
for i in range(len(nums)):
if i > 0 and nums[i] == nums[i - 1]: continue
l, r = i + 1, len(nums) - 1
while l < r:
sm = nums[i] + nums[l] + nums[r]
if abs(sm - target) < diff: diff, res = abs(sm - target), sm
if sm < target: l += 1
elif sm > target: r -= 1
else: return res
return res
Input
nums = [0,0,0], target = 1
#6 Code Example with C# Programming
Code -
C# Programming
using System;
namespace LeetCode
{
public class _016_3SumClosest
{
public int ThreeSumClosest(int[] nums, int target)
{
Suffle(nums);
Quick3WaySort(nums, 0, nums.Length - 1);
int result = 0, rest = int.MaxValue;
int sumValue = 0;
var tempRest = 0;
int lo = 0, hi = 0;
for (var index = 0; index < nums.Length - 2; index++)
{
lo = index + 1;
hi = nums.Length - 1;
while (lo < hi)
{
sumValue = nums[index] + nums[lo] + nums[hi];
tempRest = target - sumValue;
if (tempRest == 0) { return sumValue; }
tempRest = tempRest < 0 ? -tempRest : tempRest;
if (tempRest < rest)
{
rest = tempRest;
result = sumValue;
}
if (sumValue < target)
{
do
{
lo++;
} while (lo < hi && nums[lo - 1] == nums[lo]);
}
else if (sumValue > target)
{
do
{
hi--;
} while (lo < hi && nums[hi + 1] == nums[hi]);
}
else
{
do
{
lo++;
} while (lo < hi && nums[lo - 1] == nums[lo]);
do
{
hi--;
} while (lo < hi && nums[hi + 1] == nums[hi]);
}
}
while (index < nums.Length - 3 && nums[index + 1] == nums[index])
{
index++;
}
}
return result;
}
void Suffle(int[] nums)
{
var random = new Random();
int N = nums.Length;
int r, temp;
for (int i = 0; i < N; i++)
{
r = random.Next(i + 1);
temp = nums[r];
nums[r] = nums[i];
nums[i] = temp;
}
}
void Quick3WaySort(int[] nums, int lo, int hi)
{
if (lo >= hi) { return; }
var lt = lo;
var gt = hi;
var i = lo;
var v = nums[i];
int temp;
while (i < = gt)
{
if (nums[i] > v)
{
temp = nums[i];
nums[i] = nums[gt];
nums[gt--] = temp;
}
else if (nums[i] < v)
{
temp = nums[i];
nums[i] = nums[lt];
nums[lt++] = temp;
}
else { i++; }
}
Quick3WaySort(nums, lo, lt - 1);
Quick3WaySort(nums, gt + 1, hi);
}
}
}
Input
nums = [-1,2,1,-4], target = 1
Output
2