## Algorithm

Problem Name: 16. 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;
}
``````
Copy The Code &

Input

cmd
nums = [-1,2,1,-4], target = 1

Output

cmd
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;
}
};
``````
Copy The Code &

Input

cmd
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;
}
}
``````
Copy The Code &

Input

cmd
nums = [-1,2,1,-4], target = 1

Output

cmd
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;
};
``````
Copy The Code &

Input

cmd
nums = [0,0,0], target = 1

Output

cmd
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
``````
Copy The Code &

Input

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

``````
Copy The Code &

Input

cmd
nums = [-1,2,1,-4], target = 1

Output

cmd
2