# leetcode war 16 - 3Sum closest

2017-10-06

https://leetcode.com/problems/3sum-closest/description/

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

``````For example, given array S = {-1 2 1 -4}, and target = 1.

The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).``````

# analysis

we've done a special version of this problem, which target is 0 in previous problem: [leetcode war 15 - 3Sum])(http://tech.colla.me/en/show/leetcode_war_15_3Sum)

so instead of 0, we have to consider a generic form of solution.

we also sort this and traverse all the numbers by placing them as the middle one:

``````let s = num[i] + num[j] + num[k]

if s > target
we have to move k to k-1, num[i] + num[j] + num[k-1],
if s < target
we have to move i to i+ 1, num[i + 1] + num[j] + num[k]``````

this will have the same O(n2) as the last one

# solution 1 two cursors

``````/**
* @param {number[]} nums
* @return {number[][]}
*/
var threeSumClosest = function(nums, target) {
var result = [];
var closestDistance = Infinity;

// first lets sort the array
nums.sort(function(a, b) {
if (a < b) {
return -1;
}

if (a > b) {
return 1;
}

return 0;
});

if (nums.length < 3) {
return result;
}

var distance = 0;
var sum = 0;
// try every number as the middle one
for (var i = 1, max = nums.length - 1; i < max; i++) {
var j = 0;
var k = nums.length - 1;

// if encounter two same numbers
// we can skip checking j < i - 1
if (nums[i] === nums[i - 1]) {
j = i - 1;
}

while (j < i && k > i) {
sum = nums[j] + nums[i] + nums[k];
distance = Math.abs(sum - target);

if (distance < closestDistance) {
result = sum;
closestDistance = distance;

if (distance === 0) {
break;
}

// for case like -1 -1 2
// we should move the middle number just right to the next different value
// because the triple is already collected
if (nums[j] === nums[i]) {
while (i < max && nums[i + 1] === nums[i]) {
i++;
}
}
}

if (sum <= target) {
j++;
while (j < i && nums[j] === nums[j - 1]) {
j++;
}
}

if (sum >= target) {
k--;
while (k > i && nums[k] === nums[k + 1]) {
k--;
}
}
}
}

return result;
};``````

well it basically is the same as the last one. except that we are caching the closest number, rather than comparing to 0;

this solution ranks top 30%, not that bad ? 