在JavaScript中将O(n ^ 3)更改为O(n ^ 2)

Question

我正试图在我的编码解决方案中节省时间.

我有一个函数调用tripletSum,它接受两个参数x,a其中x是一个数字,a是一个数组.

true如果列表a包含三个加起来的元素,则该函数应该返回x,否则它应该返回false.

我创建了以下工作解决方案:

function tripletSum(x, a) {
    for(var i = 0; i < a.length; i++) {
        for(var j = i + 1; j < a.length; j++) {
            for(var k = j + 1; k < a.length; k++) {
                if((a[i] + a[j] + a[k]) === x) {
                    return true;
                }
            }
        }
    }
    return false;
}

但这似乎不是最好的做法.目前,运行此功能所需的时间是,O(n^3)如果我没有弄错,我认为可以改进它的时间复杂度O(n^2).

无论如何,我可以更改此代码来做到这一点？

编辑:这不是另一个问题的重复,因为我要求对我当前的JavaScript示例进行具体改进,这不是它在标记的重复问题中提出的要求.

Answer 1

为数组中包含的所有键保留一个类似于字典的对象。然后在第二个循环中，从x中减去两个值，然后在字典中查找该值。

function tripletSum(x, a) {
    var dictionary = {};
    for(var i = 0; i < a.length; i++) {
        dictionary[a[i]] = true;
    }

    for(var i = 0; i < a.length; i++) {
        for(var j = i + 1; j < a.length; j++) {
            var remainder = x - a[i] - a[j];
            if(dictionary[remainder])
                return true;
        }
    }
    return false;
}

Answer 2

想法是：首先需要对数组进行排序a。之后，您可以使用一个循环来迭代从 0 到 N - 2（唯一）的所有元素。我们称i这个循环为索引。这就是数组已排序这一事实的用处。我们将利用数组已排序的知识来“压缩”“未处理”的子数组（范围从 i + 1 到第 N 个元素）。您现在将有 2 个值left和right。left将指示未处理子数组的左索引，而right将指示数组中未处理部分的右索引。一开始我们设置left = i + 1和right = N - 1。我们计算sum a[i] + a[left] + a[right]. 现在我们有3个案例：

1. If sum = x然后返回真
2. 如果sum > x那么我们需要使总和更低，那么我们需要减right1（从右挤压）
3. 如果sum < x我们需要使总和更大，那么我们需要增加left（1从左边挤压）

下面是 Javascript 解决方案。

function tripletSum(x, a) {
    a.sort(function(i, j) {
        return i - j;
    });

    var N = a.length;

    for(var i = 0; i < N - 2; i++) {
        var left = i + 1, right = N - 1;

        while(left < right) {
            var sum = a[i] + a[left] + a[right];
            if(sum === x) {
                return true;
            }
            else if(sum > x) {
                right--;
            }
            else {
                left++;
            }
        }

    }

    return false;
}

时间复杂度为 ，O(N^2)并且没有使用额外的空间。