JavaScript O(n²) time and space using map


  • 0
    var fourSumCount = function(A, B, C, D) {
        const left = {};
        for (let a of A) {
            for (let b of B) {
                left[a + b] = (left[a + b] || 0) + 1;
            }
        }
        let count = 0;
        for (let c of C) {
            for (let d of D) {
                count += left[-c - d] || 0;
            }
        }
        return count;
    };
    

    The basic idea is: the paths through the column vectors A, B, C, and D with zero sum can be found by first counting the paths halfway through with sum A[i] + B[j] and then checking if their additive inverses exist as C[k] + D[l].

    And of course here is the two-liner version:

    var fourSumCount = function(A, B, C, D) {
        const left = A.reduce((left, a) => B.reduce((left, b) => (left[a + b] = (left[a + b] || 0) + 1, left), left), {});
        return C.reduce((count, c) => D.reduce((count, d) => count + (left[-c - d] || 0), count), 0);
    };
    

Log in to reply
 

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