时间戳

首页 > 解决方案 > 查找三个数字的目标总和 - 优化嵌套循环

javascript - 查找三个数字的目标总和 - 优化嵌套循环

问题描述

我有一个问题，给定一个整数数组，我需要找到三个加起来等于零的数字的集合。下面的解决方案有效，但并不像我想要的那样最佳，我正在寻找优化它的方法以避免不必要的处理。

我在下面做的是迭代所有数字组合，同时消除对每个嵌套循环中相同索引的迭代，我正在检查最内层循环中的三个数字是否加起来为零。如果是，我将数组转换为字符串，如果字符串不在结果数组中，我将添加它。在返回之前，我将字符串转换回数组。

我很感激有关如何进一步优化这一点的任何建议，或者如果我错过了一些更好地实施的机会。我不是在寻找一个完整的重构，只是一些可以提高性能的调整。

var threeSum = function(nums) {
    const sorted = nums.sort();

    if(sorted.length && (sorted[0] > 0 || sorted[sorted.length-1] < 0)) {
        return [];
    }

    let result = [];

    for(let i=0; i < sorted.length; i++) {
        for(let z=i+1; z < sorted.length; z++) {
            for(let q=z+1; q < sorted.length; q++) {
                if(sorted[i]+sorted[z]+sorted[q] === 0) {
                    const temp = [sorted[i], sorted[z], sorted[q]].join(',');

                    if(!result.includes(temp)) {
                        result.push(temp);
                    }
                }
            }
        }
    }

    return result.map(str => str.split(','));
};

样本输入：[-1,0,1,2,-1,-4]

预期输出：[[-1,-1,2],[-1,0,1]]

标签： javascript

解决方案

OP 的解决方案可以O(N³)及时运行，无需额外存储。

经典的“使用哈希表”解决方案来查找丢失的元素可以通过存储来O(N²)缩短时间。O(N)

该解决方案涉及使用对象构建数字映射。（您也可以使用 Map 对象，但是您不能使用++and--运算符来表达）。然后只是一个普通的循环和内部循环来评估所有的对。对于每一对，找出这些对的负和是否在地图中。

function threeSum(nums) {

    var nummap = {};    // map a value to the number of ocurrances in nums
    var solutions = new Set(); // map of solutions as strings

    // map each value in nums into the number map
    nums.forEach((val) => {
        var k = nummap[val] ? nummap[val] : 0; // k is the number of times val appears in nummap
        nummap[val] = k+1; // increment by 1 and update
    });

    // for each pair of numbers, see if we can find a solution the number map
    for (let i = 0; i < nums.length; i++) {

        var ival = nums[i];
        nummap[ival]--;

        for (let j = i+1; j < nums.length; j++) {
            var jval = nums[j];
            nummap[jval]--;

            var target = -(ival + jval); // this could compute "-0", but it works itself out since 0==-0 and toString will strip the negative off

            // if target is in the number map, we have a solution
            if (nummap[target]) {

                // sort this three sum solution and insert into map of available solutions
                // we do this to filter out duplicate solutions
                var tmp = [];
                tmp[0] = ival;
                tmp[1] = jval;
                tmp[2] = target;

                tmp.sort();
                solutions.add(tmp.toString());
            }

            nummap[jval]++; // restore original instance count in nummap
        }
        nummap[ival]--;
    }

    for (s of solutions.keys()) {
        console.log(s);
    }

}

threeSum([9,8,7,-15, -9,0]);

推荐阅读