all articles

leetcode war 16 - 3Sum closest

2017-10-06 @sunderls

leetCode js

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 ?