N数之和 通解

sum-of-n-numbers.js

function threeSum(nums, target) {
    return uniq(findN(nums.sort(sortor), target, 3));
};

function fourSum(nums, target) {
    return uniq(findN(nums.sort(sortor), target, 4));
};


function findN(nums, target, count, startIndex = 0) {
    if (count < 3) return findTwo(nums, target, startIndex);
    return nums.reduce(function (ret, val, i) {
        if (i < startIndex) return ret;
        let result = findN(nums, target - val, count - 1, i + 1);
        return ret.concat(result.map(a => [val, ...a]));
    }, []);
}

function findTwo(nums, target, startIndex = 0) {
    let left = startIndex;
    let right = nums.length - 1;
    let matched = [];
    while (left < right) {
        while (nums[left] == nums[left + 2]) left++;
        while (right - 2 >= startIndex && nums[right] == nums[right - 2]) right--;
        let val = nums[left] + nums[right];
        if (val > target) right--;
        if (val < target) left++;
        if (val == target) {
            matched.push([nums[left++], nums[right--]]);
        }
    }
    return matched;
}

function sortor(a, b) {
    return a > b ? 1 : -1;
}

function uniq(tuples) {
    let map = {};
    let ret = [];
    for (let i = 0; i < tuples.length; i++) {
        if (!map[tuples[i]]) {
            ret.push(tuples[i]);
            map[tuples[i]] = true;
        }
    }
    return ret;
}

function uniq2(tuples) {
    let map = {};
    let ret = [];
    for (let j = 0; j < tuples.length; j++) {
        let t = tuples[j];
        let i = 0;
        let current = map;
        while (i < t.length) {
            if (!current[t[i]]) {
                current[t[i]] = i + 1 === t.length ? true : {};
            }
            else if (i + 1 === t.length) {
                i = 0;
                break;
            }
            current = current[t[i++]];
        }
        if (i) {
            ret.push(t);
        }
    }
    return ret;
}