Short JavaScript using several maps


  • 0
    var fourSum = function(nums, target) {
        const counts = new Map();  // counts of elements in `nums`
        const aPlusB = new Map();  // sum tuples e.g. 5 => [[2, 3], [1, 4], ... ]
        for (let i = 0; i < nums.length - 1; i++) {
            counts.set(nums[i], (counts.get(nums[i]) || 0) + 1);
            for (let j = i + 1; j < nums.length; j++) {
                let a = nums[i], b = nums[j];
                aPlusB.set(a + b, [...aPlusB.get(a + b) || [], [a, b]]);
            }
        }
        counts.set(nums[nums.length - 1], (counts.get(nums[nums.length - 1]) || 0) + 1);
        const res = new Set();  // Sets are unique, so no worries about duplicates
        for (let i = 0; i < nums.length - 1; i++) {
            for (let j = i + 1; j < nums.length; j++) {
                let c = nums[i], d = nums[j];
                if (!aPlusB.has(target - c - d)) continue;  // move on if wrong sum
                aPlusB.get(target - c - d)
                    .forEach(ab => {
                        const abcd = [...ab, c, d];
                        if (!abcd.some(e => abcd.reduce((qty, a) => qty + (a === e), 0) > counts.get(e))) {
                            res.add(abcd.sort().join(','));
                        }
                    });
            }
        }
        return [...res].map(abcd => abcd.split(',').map(e => parseInt(e)));
    };
    

    This isn't particularly fast but gets the job done.

    1. Remember the [a, b] pairs keyed by their sum.
    2. Find the [c, d] tuple which satisfies a + b + c + d = target.
    3. If nums can supply the 4-tuple, add [a, b, c, d] to the unique set of results keyed by their sorted value.

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.