求和问题

[RubyLouvre]

3sum

使用回溯法

function threeSum(nums) {
    var result = [],
        condidate = [],
        target = 0;
        nums.sort((a,b)=>a-b)
    function backtrack(start) {
        if (condidate.length === 3 && target == 0) {
            result.push(condidate.concat());
        } else {
            for (var i = start; i < nums.length; i++) {
                if(i != start && nums[i] == nums[i-1]){
                    continue
                }
                var el = nums[i]
                condidate.push(el);
                target += el
                backtrack(i + 1);
                target -= el
                condidate.pop();
            }
        }
    }
    backtrack(0); 
    return result;
}
threeSum( [-1, 0, 1, 2, -1, -4]);

超时 使用hash法

function twoSum(nums, target) {
    var hash = {};
    var result = [];
    for (var i = 0; i < nums.length; i++) {
        var num = nums[i];
        if (num in hash) {
            result.push([0 - target, target - num, num]);
        } else {
            hash[target - num] = num;
        }
    }
    return result;
}
function threeSum(nums) {
    var result = [], hash = {}
    nums.sort((a, b) => a - b);
    for (var i = 0; i < nums.length; i++) {
        var s = twoSum(nums.slice(i + 1), 0 - nums[i]);
        s.forEach(function(el){
            if(!hash[el]){
                hash[el] = 1;
                result.push(el)
            }
        })
    }
    console.log(result)
    return result;
}
threeSum([-1, 0, 1, 2, -1, -4]);

超时

[RubyLouvre]

2sum

左右指针法

function twoSum(nums, target) {
    var result = [];
    nums.sort((a, b) => a - b);
    var i =0, j = nums.length - 1;
    while (i < j) {
        var sum = nums[i] + nums[j];
        if (sum == target) {
            result.push([nums[i], nums[j]]);
            //处理重复的情况
            i++;
            j--;
            while (i < j && nums[i] == nums[i - 1]) i++;
            while (i < j && nums[j + 1] == nums[j]) j--;
        } else if (sum < target) {
            i++;
        } else {
            j--;
        }
    }
    // console.log(result)
    return result;
}

twoSum( [2, 7, 11, 15], 9)

[RubyLouvre]

3sum

上面的变形， twoSum有两个参数，数组与目标值。而3sum则目标值是默认为零， 因此我们从3sum的数组截出一些子数组出来，然后将第一个nums[i]默认为-target, 再找两个数，让它们的和等于target，这样相加就是零。

function threeSum(nums) {
    nums.sort((a, b) => a - b);
    var res = [];

    if (nums.length < 3 || nums[0] > 0 || nums[nums.length - 1] < 0) {
        return res;
    }
    for (var i = 0; i < nums.length; i++) {
        if (i > 0 && nums[i] == nums[i - 1]) {
            continue;
        }
        twoSum(nums, i, res); //相当于twoSum(nums, 0, i, res)，target总是为零
    }
    console.log(res);
    return res;
}
function twoSum(nums, targetIndex, res) {
    var left = targetIndex + 1, target = nums[targetIndex]
        right = nums.length - 1;
    while (left < right) {
        let sum =  nums[left] + nums[right] + target
        if (sum == 0) {
            var temp = [target, nums[left], nums[right]];
            res.push(temp);

            //去重
            while (left < right && nums[left] == nums[left + 1]) left++;
            while (left < right && nums[right] == nums[left - 1]) right--;

            left++;
            right--;
        } else if (sum > 0) {
            right--;
        } else if (sum < 0) {
            left++;
        }
    }
}
threeSum([-1, 0, 1, 2, -1, -4]);

[RubyLouvre]

4sum

function twoSum(nums, numsSize, start, target) {
    var l = start,
        r = numsSize - 1,
        res = []
    while (l < r) {
        var sum = nums[l] + nums[r];
        if (sum == target) {
            res.push([nums[l], nums[r]]);
            //去重
            while (l < r && nums[l] == nums[l + 1]) l++;
            while (l < r && nums[r] == nums[r - 1]) r--;
            l++;
            r--;
        } else if (sum > target) {
            r--;
        } else {
            l++;
        }
    }
    return res;
}

function kSum(nums, numsSize, start, k, target) {
    if (k == 2) {
        return twoSum(nums, numsSize, start, target);
    } else {
        var kSumRes = [];
        for (var i = start; i < numsSize; i++) {
            if (i > start && nums[i] == nums[i - 1]) {
                continue;
            }
            var item = kSum(nums, numsSize, i + 1, k - 1, target - nums[i]); //降维
            var itemSize = item.length;
            for (var j = 0; j < itemSize; j++) {
                item[j].unshift(nums[i]);
                kSumRes.push(item[j]);
            }
        }
        console.log(kSumRes)
        return kSumRes;
    }
}
function threeSum(nums){
    if(Object(nums).length < 3){
        return []
    }
    nums.sort((a,b)=>a - b)
    return kSum(nums, nums.length, 0, 3, 0 );
}
threeSum([-1, 0, 1, 2, -1, -4])

[RubyLouvre]

LeetCode 259. 3Sum Smaller

求三数之和小于一个目标值

function threeSumSmaller(nums, target){
    if(Object(nums).length < 3){
        return []
    }

    nums.sort((a, b)=> a-b);
    if(nums[0] >= target){
        return []
    }
    var sum = 0,condidtate = [],result = []
    function backtrack(start){
        if(condidtate.length == 3){
            if(sum < target){
                result.push(condidtate.concat())
            }
        }else{
            for(var i = start; i < nums.length; i++){
                sum += nums[i]
                condidtate.push(nums[i])
                backtrack(i+1)
                sum -= nums[i]
                condidtate.pop()
            }
        }
    }
    backtrack(0)
    console.log(result)
    return result;
}
threeSumSmaller([-2, 0, 1, 3], 2)

[RubyLouvre]

LeetCode 16 3Sum Closest

求最接近给定值的三数之和

Given an array nums of n integers 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:

Given array nums = [-1, 2, 1, -4], and target = 1.

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

function threeSumClosest(nums, target) {
    nums.sort((a, b) => a - b);
    var end = nums.length;
    var val = 0, sum = Infinity
    function backtrack(start, n) {
        if (n == 3) {
            if(Math.abs(val - target) < Math.abs(sum - target)){
                sum =  val
            }
        } else {
            for (var i = start; i < nums.length; i++) {
                val += nums[i];
                backtrack(i + 1, n+1)
                val -= nums[i];
            }
        }
    }
    backtrack(0, 0);
    console.log(sum);
    return sum;
}

threeSumClosest([-1, 2, 1 ,-4], 1);