ein Array gegeben, bestimmen Sie bitte, ob es drei Zahlen enthält, deren Summe gleich auf 0

Question

einem Array erhalten Sie bestimmen, ob es drei Zahlen enthält, deren Summe gleich zu 0.

Java

ich könnte leicht denken an eine Brute-Force-Lösung

public class HelloWorld { 
    public static void main(String[] args) { 
    int[]arr = {2, 3, 4, 5, 6, 7, -7, 0, -9}; 
    boolean found = false; 
    for(int x = 0; x < arr.length; x++){ 
     for(int y = 0; y < arr.length; y++){ 
      for(int z = 0; z < arr.length; z++){ 
       if(arr[x] + arr[y] + arr[z] == 0){ 
       found = true; 
       break; 
       } 
      } 
     } 
    } 
    if(found){ 
     System.out.println("Was found"); 
    } else{ 
     System.out.println("Was not found"); 
    } 
    } 
} 

Dies ist eindeutig O(N^3) aber wie kann ich es besser machen?

Answer 1

Ein wenig wird bessere Lösung:

int[]arr = {2, 3, 4, 5, 6, 7, -7, 0, -9}; 
    boolean found = false; 
    for(int x = 0; x < arr.length-3; x++){ 
     for (int y = x+1; y < arr.length - 2; y++){ 
      for (int z = y+1; z < arr.length; z++){ 
       if(arr[x] + arr[y] + arr[z] == 0){ 
        found = true; 
        break; 
        } 
      } 
     } 
    } 
    if(found){ 
     System.out.println("Was found"); 
    } else{ 
     System.out.println("Was not found"); 
    } 
    } 

Sie haben nicht die gleiche Anzahl an sich selbst wieder hinzufügen müssen.

Daher können Sie y = x+1 und z = y+1 verwenden.

Eine andere besser O(n^2) Lösung ist so etwas, das verwendet Sortierung:

class FindTriplet 
{ 

    // returns true if there is triplet with sum equal 
    // to 'sum' present in A[]. Also, prints the triplet 
    boolean find3Numbers(int A[], int arr_size, int sum) 
    { 
     int l, r; 

     /* Sort the elements */ 
     quickSort(A, 0, arr_size - 1); 

     /* Now fix the first element one by one and find the 
      other two elements */ 
     for (int i = 0; i < arr_size - 2; i++) 
     { 
      // To find the other two elements, start two index variables 
      // from two corners of the array and move them toward each 
      // other 
      l = i + 1; // index of the first element in the remaining elements 
      r = arr_size - 1; // index of the last element 
      while (l < r) 
      { 
       if (A[i] + A[l] + A[r] == sum) 
       { 
        System.out.print("Triplet is " + A[i] + " ," + A[l] 
          + " ," + A[r]); 
        return true; 
       } 
       else if (A[i] + A[l] + A[r] < sum) 
        l++; 

       else // A[i] + A[l] + A[r] > sum 
        r--; 
      } 
     } 

     // If we reach here, then no triplet was found 
     return false; 
    } 

    int partition(int A[], int si, int ei) 
    { 
     int x = A[ei]; 
     int i = (si - 1); 
     int j; 

     for (j = si; j <= ei - 1; j++) 
     { 
      if (A[j] <= x) 
      { 
       i++; 
       int temp = A[i]; 
       A[i] = A[j]; 
       A[j] = temp; 
      } 
     } 
     int temp = A[i + 1]; 
     A[i + 1] = A[ei]; 
     A[ei] = temp; 
     return (i + 1); 
    } 

    /* Implementation of Quick Sort 
    A[] --> Array to be sorted 
    si --> Starting index 
    ei --> Ending index 
    */ 
    void quickSort(int A[], int si, int ei) 
    { 
     int pi; 

     /* Partitioning index */ 
     if (si < ei) 
     { 
      pi = partition(A, si, ei); 
      quickSort(A, si, pi - 1); 
      quickSort(A, pi + 1, ei); 
     } 
    } 

    // Driver program to test above functions 
    public static void main(String[] args) 
    { 
     FindTriplet triplet = new FindTriplet(); 
     int A[] = {1, 4, 45, 6, 10, 8}; 
     int sum = 0; // this is what you are looking for 
     int arr_size = A.length; 

     triplet.find3Numbers(A, arr_size, sum); 
    } 
} 

Fort mehr hier lesen:

http://www.geeksforgeeks.org/find-a-triplet-that-sum-to-a-given-value/