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];


functionfindTriples(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 = [...newSet(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.

functionthreeSum (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-negativefor (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 negativefor (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-0if (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 ofchooseN(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 -

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

const chooseN = function* (n = 0, iter = [])
{ const loop = function* (r, m, i)
  { if (m === 0) returnyield r
    if (i >= iter.length) returnyield* 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 -

constsum = (nums = []) =>
  nums.reduce((r, num) => r + num, 0)
  
const chooseN = function* (n = 0, iter = [])
{ const loop = function* (r, m, i)
  { if (m === 0) returnyield r
    if (i >= iter.length) returnyield* 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 ofchooseN(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 -

constchooseN = (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))

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

constsolver = (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]]