Zmiana O (n^3) na O (n^2) w JavaScript

Question

Próbuję zawinąć głowę oszczędzając czas w moim rozwiązaniu kodowania.

Mam funkcję zwaną tripletSum który ma dwa parametry x i a gdzie x jest liczbą i a jest tablicą.

Funkcja ta ma powrócić true jeśli lista a zawiera trzy elementy, które sumują się do liczby x, w przeciwnym razie należy zwrócić false.

Utworzyłem następujące Roztwór roboczy:

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; 
} 

Ale to nie wydaje się najlepszą praktyką. Obecnie czas potrzebny na uruchomienie tej funkcji to O(n^3), jeśli się nie mylę i myślę, że można ją poprawić, aby mieć złożoność czasową O(n^2).

W każdym razie mogę zmienić ten kod, aby to zrobić?

Edit: To nie jest duplikat innej kwestii, bo prosił o konkretnej poprawy na moim obecnym przykład w JavaScript, który nie jest co poprosił w oznaczonym duplikatu pytanie.

Answer 1

Oto pomysł: ty Najpierw trzeba posortować tablicę a. Następnie możesz mieć jedną pętlę, która iteruje przez wszystkie elementy od 0 do N - 2 (wyłącznie). Zadzwońmy pod numer i indeks tej pętli. Tutaj przychodzi użyteczność faktu, że tablica jest posortowana. Wykorzystamy wiedzę, że tablica jest posortowana w celu "wyciśnięcia" "podobrazia" nieprzetworzonego (zakres od i + 1 do N-tego elementu). Będziesz teraz miał 2 wartości: left i right. left będzie wskazywał lewy indeks nieprzetworzonej subarray, a right wskaże odpowiedni indeks nieprzetworzonej części tablicy. Na początku ustawiamy left = i + 1 i right = N - 1. Obliczamy wartość suma[i] + a[left] + a[right].Teraz mamy 3 przypadki:

1. If sum = x następnie powrócić prawda
2. Jeśli sum > x wtedy musimy dokonać suma mniejsza, więc musimy zmniejszyć right o 1 (wycisnąć z prawej)
3. Jeśli sum < x potem potrzeba, aby suma większa, więc musimy zwiększać left przez 1 (squeeze od lewej)

Tu następuje rozwiązanie 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; 
} 

Złożoność czasu wynosi O(N^2) i nie jest używana żadna dodatkowa przestrzeń.

Answer 2

Zachowaj obiekt podobny do słownika dla wszystkich kluczy zawartych w tablicy. Następnie w drugiej pętli odejmij dwie wartości od x i poszukaj tej wartości w słowniku.

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

Można w zasadzie wykorzystania wyszukiwania binarnego i swego celu zmniejszenia złożoności O (n^2 * logn) z O (n^3).

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 
 
]))

całkowita złożoność = O (n * logn) + O (n^2 * logn) ~ O (n^2 * logn)