如何计算javascript或3sum中3个元素的总和？

Question

我正在尝试解决此问题给定一个由 n 个整数组成的数组，在 num 中是否存在元素 a、b、c 使得 a + b + c = 0？找到数组中所有唯一的三元组，其总和为零。 var threeSum = function(nums) {    let result = [],        target = 0;    if(nums.length < 3) return result;    nums.sort((a,b)=>a-b);    console.log(nums);    for (let i = 0; i < nums.length -2 ; i++) {        if(nums[i] > target) break;        if( i > 0&& nums[i] == nums[i-1]) continue;        let j = i + 1;        let k = nums.length - 1;        while (j < k){            let sum = nums[i] + nums[j] + nums[k];            if(sum === target){                result.push([nums[i,nums[j],nums[k]]])                j++;                k--            }else if(sum < target){                j++            }else {                k--            }        }    }return result};输入和输出Given array nums = [-1, 0, 1, 2, -1, -4],A solution set is:[  [-1, 0, 1],  [-1, -1, 2]]当我调用我的函数时控制台.log（三个结果（[-1， 0， 1， 2， -1， -4]））我得到stack overflow exception

Answer 1

我们可以实现接受一个数字数组，并循环访问 所有的可能性 ， 的 。当 等于 时，产量solverpchooseN(3, nums)sum(p)0p -

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

现在我们实施和sumchooseN -

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

如果你还没有了解JavaScript的生成器，请不要担心。您也可以使用直接样式执行此操作 -

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

Answer 2

这是一个解决方案..不是最佳的，但有效...

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

Answer 3

一个有点幼稚的解决方案，没有太多考虑效率，将给定的数组分成负数和非负数数组。

总和为 0 的三元组必须正好有 2 个负数或 2 个非负数，唯一的例外是 。(0,0,0)

因此，如果否定和是相应其他数组的元素，请检查从负数或非负数中获取的所有对，如果成立，则添加三元组。

记住在上面的步骤中选择的单个数字可以防止结果数组中的重复。

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