在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）