在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

这里的理念是：你首先需要对数组a进行排序。之后，您可以有一个循环遍历从0到N - 2（唯一）的所有元素。我们打电话i这个循环的索引。这里是数组排序的事实的有用性。我们将使用数组排序的知识来“挤压”“未处理”的子阵列（范围从i + 1到第N个元素）。您现在将有2个值left和right。 left将指示未处理的子阵列的左侧索引，而right将指示数组的未处理部分的右侧索引。在开始时，我们设置了left = i + 1和right = N - 1。我们计算suma[i] + a[left] + a[right]。现在我们有三种情况：

1. If sum = x然后
2. 如果sum > x那么我们需要做的和较低的返回true，所以我们需要通过1（挤右一）递减right
3. 如果sum < x那么我们需要使总和更大，所以我们需要增加left1（从左边挤压）

以下是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)并且没有使用额外的空间。

Answer 2

为包含在数组中的所有键保留一个类似字典的对象。然后在第二个循环中，从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 3

你基本上可以利用二进制搜索和排序来降低从O（n^3）到O（n^2 * logn）的复杂度。

function tripletSum(x, a) { 
 
    a.sort(function(a, b) { 
 
      return a - b 
 
     }) // O(n*logn) 
 
    var n = a.length; 
 
    for (var i = 0; i < n; i++) { 
 
     for (var j = i + 1; j < n; j++) { 
 
      if (a.indexOf(x - a[i] - a[j]) > j) { 
 
       return true; //O(n^2*logn) 
 
      } 
 
     } 
 
    } 
 
    return false; 
 
} 
 

 
console.log(tripletSum(0, [ 
 
    1, 
 
    5, 
 
    6, 
 
    -2, 
 
    -3 
 
]))

总复杂= O（N * LOGN）+ O（N^2 * LOGN）〜O（N^2 * LOGN）