如何计算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))&nbsp; &nbsp; if (sum(p) === 0)&nbsp; &nbsp; &nbsp; yield p}const result =&nbsp; 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 = []) =>&nbsp; nums.reduce((r, num) => r + num, 0)const chooseN = function* (n = 0, iter = []){ const loop = function* (r, m, i)&nbsp; { if (m === 0) return yield r&nbsp; &nbsp; if (i >= iter.length) return&nbsp; &nbsp; yield* loop([...r, iter[i]], m - 1, i + 1)&nbsp; &nbsp; yield* loop(r, m, i + 1)&nbsp; }&nbsp; yield* loop([], n, 0)}在下面的浏览器中运行代码 -const sum = (nums = []) =>&nbsp; nums.reduce((r, num) => r + num, 0)&nbsp;&nbsp;const chooseN = function* (n = 0, iter = []){ const loop = function* (r, m, i)&nbsp; { if (m === 0) return yield r&nbsp; &nbsp; if (i >= iter.length) return&nbsp; &nbsp; yield* loop([...r, iter[i]], m - 1, i + 1)&nbsp; &nbsp; yield* loop(r, m, i + 1)&nbsp; }&nbsp; yield* loop([], n, 0)}const solver = function* (nums = []){ for (const p of chooseN(3, nums))&nbsp; &nbsp; if (sum(p) === 0)&nbsp; &nbsp; &nbsp; yield p}const result =&nbsp; 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 = []) =>&nbsp; n <= 0&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; // base&nbsp; &nbsp; ? [r]: x === undefined&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;// inductive: n > 0&nbsp; &nbsp; ? []: chooseN(n - 1, more, [...r, x]) // inductive: n > 0, iterable is not empty&nbsp; &nbsp; .concat(chooseN(n, more, r))const sum = (nums = []) =>&nbsp; nums.reduce((r, num) => r + num, 0)const solver = (nums = []) =>&nbsp; chooseN(3, nums)&nbsp; &nbsp; .filter(p => sum(p) === 0)const result =&nbsp; 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){&nbsp; &nbsp; let target = [];&nbsp; &nbsp; for(let i=0; i<arr.length; i++){&nbsp; &nbsp; &nbsp; &nbsp; for(let j=0; j<arr.length; j++){&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; for(let k=0; k<arr.length; k++){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if((arr[i] + arr[j] + arr[k]) == t){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; target.push([arr[i], arr[j], arr[k]]);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; target = target.map(a => a.sort()).map(i => i.join(","));&nbsp; &nbsp; target = [...new Set(target)];&nbsp; &nbsp; return target.map(i => i.split(","));}console.log(findTriples(nums, 0));

Answer 3

一个有点幼稚的解决方案，没有太多考虑效率，将给定的数组分成负数和非负数数组。总和为 0 的三元组必须正好有 2 个负数或 2 个非负数，唯一的例外是 。(0,0,0)因此，如果否定和是相应其他数组的元素，请检查从负数或非负数中获取的所有对，如果成立，则添加三元组。记住在上面的步骤中选择的单个数字可以防止结果数组中的重复。function threeSum (nums) {&nbsp; &nbsp; let result = []&nbsp; &nbsp; &nbsp; , an_pos = []&nbsp; &nbsp; &nbsp; , an_neg = []&nbsp; &nbsp; &nbsp; , bdict_seen = {}&nbsp; &nbsp; &nbsp; , n_gotcha&nbsp; &nbsp; &nbsp; , n_zerocount = 0&nbsp; &nbsp; &nbsp; ;&nbsp; &nbsp; // Shortcut for short arrays ...&nbsp; &nbsp; console.log ( nums + ' ...' );&nbsp; &nbsp; if ( nums.length < 3) {&nbsp; &nbsp; &nbsp; &nbsp; console.log('... []');&nbsp; &nbsp; &nbsp; &nbsp; return result;&nbsp; &nbsp; }&nbsp; &nbsp; // Partition source array into negatives and non-negatives&nbsp; &nbsp; nums.forEach ( (pn_number) => {&nbsp; &nbsp; &nbsp; &nbsp; if ( pn_number < 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; an_neg.push(pn_number);&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; an_pos.push(pn_number);&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (pn_number === 0) { n_zerocount++; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; });&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; // 2 negatives, 1 non-negative&nbsp; &nbsp; for (let i = 0; i < an_neg.length-1; i++) {&nbsp; &nbsp; &nbsp; &nbsp; for (let j = i+1; j < an_neg.length; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (n_gotcha = an_pos.find ( pn_pos => pn_pos === -(an_neg[i] + an_neg[j]) )) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (!bdict_seen[n_gotcha]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.push ( [an_neg[i], an_neg[j], n_gotcha] );&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bdict_seen[n_gotcha] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; // 2 non-negatives, 1 negative&nbsp; &nbsp; for (let i = 0; i < an_pos.length-1; i++) {&nbsp; &nbsp; &nbsp; &nbsp; for (let j = i+1; j < an_pos.length; j++) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (n_gotcha = an_neg.find ( pn_neg => pn_neg === -(an_pos[i] + an_pos[j]) )) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if (!bdict_seen[n_gotcha]) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; result.push ( [an_pos[i], an_pos[j], n_gotcha] );&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; bdict_seen[n_gotcha] = true;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp;&nbsp;&nbsp; &nbsp; // Special case: triple-0&nbsp; &nbsp; if (n_zerocount >= 3) {&nbsp; &nbsp; &nbsp; &nbsp; result.push ( [0,0,0] );&nbsp; &nbsp; }&nbsp; &nbsp; // Sorting not needed but added for a more readable output&nbsp;&nbsp; &nbsp; result.sort ( (a,b) => a-b );&nbsp; &nbsp; console.log('... ' + JSON.stringify(result));&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; return result;} // threeSumthreeSum ( [-1, 0, 1, 2, -1, -4] );