How To Calculate The Sum Of 3 Element In Javascript Or 3sum?

I am trying to solve this problem Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives t

Solution 1:

here's a solution .. not optimal but works...

let nums = [-1, 0, 1, 2, -1, -4];


function findTriples(arr, t){
    let target = [];
    for(let i=0; i<arr.length; i++){

        for(let j=0; j<arr.length; j++){
    
            for(let k=0; k<arr.length; k++){
                
                if((arr[i] + arr[j] + arr[k]) == t){
                    target.push([arr[i], arr[j], arr[k]]);
                }
            }
    
        }

    }
    
    target = target.map(a => a.sort()).map(i => i.join(","));
    target = [...new Set(target)];
    return target.map(i => i.split(","));
}

console.log(findTriples(nums, 0));

Solution 2:

A somewhat naive solution without much regard to efficiency splits the given array into arrays of negative and non-negative numbers.

A triplet that sums up to 0 then must have exactly 2 negatives or 2 non-negatives, with the sole exception of (0,0,0).

So check for all pairs taken from either the negatives or the non-negatives if the negated sum is an element of the respective other array and add the triple if that holds.

Memorizing the single numbers selected in the above step guards against repetitions in the result array.

function threeSum (nums) {
    let result = []
      , an_pos = []
      , an_neg = []
      , bdict_seen = {}
      , n_gotcha
      , n_zerocount = 0
      ;

    // Shortcut for short arrays ...
    console.log ( nums + ' ...' );
    if ( nums.length < 3) {
        console.log('... []');
        return result;
    }

    // Partition source array into negatives and non-negatives
    nums.forEach ( (pn_number) => {
        if ( pn_number < 0) {
            an_neg.push(pn_number);
        } else {
            an_pos.push(pn_number);
            if (pn_number === 0) { n_zerocount++; }
        }
    });
    
    // 2 negatives, 1 non-negative
    for (let i = 0; i < an_neg.length-1; i++) {
        for (let j = i+1; j < an_neg.length; j++) {
            if (n_gotcha = an_pos.find ( pn_pos => pn_pos === -(an_neg[i] + an_neg[j]) )) {
                if (!bdict_seen[n_gotcha]) {
                    result.push ( [an_neg[i], an_neg[j], n_gotcha] );
                    bdict_seen[n_gotcha] = true;
                }
            }
        }
    }        

    // 2 non-negatives, 1 negative
    for (let i = 0; i < an_pos.length-1; i++) {
        for (let j = i+1; j < an_pos.length; j++) {
            if (n_gotcha = an_neg.find ( pn_neg => pn_neg === -(an_pos[i] + an_pos[j]) )) {
                if (!bdict_seen[n_gotcha]) {
                    result.push ( [an_pos[i], an_pos[j], n_gotcha] );
                    bdict_seen[n_gotcha] = true;
                }
            }
        }
    }        

    // Special case: triple-0
    if (n_zerocount >= 3) {
        result.push ( [0,0,0] );
    }

    // Sorting not needed but added for a more readable output 
    result.sort ( (a,b) => a-b );
    console.log('... ' + JSON.stringify(result));
    
    return result;
} // threeSum


threeSum ( [-1, 0, 1, 2, -1, -4] );

Solution 3:

We can implement solver to accept an array of numbers and iterate through all the possibilities, p, of chooseN(3, nums). When sum(p) is equal to 0, yield p -

const solver = function* (nums = [])
{ for (const p of chooseN(3, nums))
    if (sum(p) === 0)
      yield p
}

const result =
  Array.from(solver([-1, 0, 1, 2, -1, -4]))

console.log(result)
// [[-1, 0, 1], [-1, 2, -1], [0, 1, -1]]

Now we implement sum and chooseN -

const sum = (nums = []) =>
  nums.reduce((r, num) => r + num, 0)

const chooseN = function* (n = 0, iter = [])
{ const loop = function* (r, m, i)
  { if (m === 0) return yield r
    if (i >= iter.length) return
    yield* loop([...r, iter[i]], m - 1, i + 1)
    yield* loop(r, m, i + 1)
  }
  yield* loop([], n, 0)
}

Run the code in your browser below -

const sum = (nums = []) =>
  nums.reduce((r, num) => r + num, 0)
  
const chooseN = function* (n = 0, iter = [])
{ const loop = function* (r, m, i)
  { if (m === 0) return yield r
    if (i >= iter.length) return
    yield* loop([...r, iter[i]], m - 1, i + 1)
    yield* loop(r, m, i + 1)
  }
  yield* loop([], n, 0)
}

const solver = function* (nums = [])
{ for (const p of chooseN(3, nums))
    if (sum(p) === 0)
      yield p
}

const result =
  Array.from(solver([-1, 0, 1, 2, -1, -4]))

console.log(JSON.stringify(result))
// [[-1,0,1],[-1,2,-1],[0,1,-1]]

---

If you haven't learned about JavaScript's generators yet, don't worry. You can do this using direct style as well -

const chooseN = (n = 0, [ x, ...more ], r = []) =>
  n <= 0                          // base
    ? [r]
: x === undefined                 // inductive: n > 0
    ? []
: chooseN(n - 1, more, [...r, x]) // inductive: n > 0, iterable is not empty
    .concat(chooseN(n, more, r))

const sum = (nums = []) =>
  nums.reduce((r, num) => r + num, 0)

const solver = (nums = []) =>
  chooseN(3, nums)
    .filter(p => sum(p) === 0)

const result =
  solver([-1, 0, 1, 2, -1, -4])

console.log(JSON.stringify(result))
// [[-1,0,1],[-1,2,-1],[0,1,-1]]