Dato un array di interi ordinati, come posso trovare se esiste un insieme di 3 elementi che sommano a K?

Question

Quindi dire che ho un array ordinato:

{ 1, 2, 3, 4, 5, 6 } 

E voglio vedere se esiste tre elementi che somma a 14.

3 + 5 + 6 = 14 

Sono abbastanza sicuro che non v'è alcun modo per farlo questo in O (N) tempo, ma penso che possa essere fatto in O (N^2) in qualche modo.

Answer 1

Questo è simile al problema di somma del sottoinsieme, che è NP-Completo.
Ma limitando la lunghezza del sottoinsieme a 3, è possibile trovare una soluzione rapida.
Il tuo problema è equivalente alla 3SUM problem.
r = K come nella sua interrogazione.

Pseudocode: O (N^2)

for (i in 1..n-2) 
{ 
    j = i+1 // Start right after i. 
    k = n // Start at the end of the array. 

    while (k >= j) { 
    // done. 
    if (A[i] + A[j] + A[k] == r) return (A[i], A[j], A[k]) 

    // We didn't match. Let's try to get a little closer: 
    // If the sum was too big, decrement k. 
    // If the sum was too small, increment j. 
    (A[i] + A[j] + A[k] > r) ? k-- : j++ 
    } 
    // When the while-loop finishes, j and k have passed each other and there's 
    // no more useful combinations that we can try with this i. 
} 

Answer 2

Questo problema è simile al 3SUM problem e può fare in O(N^2). Thisjava working code esegue ciò.

// The function prints the values if there exists 3 distinct indices 
    // in the array arr that sum to req. 
    void run(){ 
     int[] arr = { 1, 2, 3, 4, 5, 6 }; 
     int req = 14; 

     // For the algorithm to work correctly, the array must be sorted 
     Arrays.sort(arr);  

     for(int i=0; i<arr.length; i++){// Iterate over the elements of the array. 

      // Check in linear time whether there exists distinct indices 
      // lo and hi that sum to req-arr[i] 
      int lo=0, hi = arr.length-1; 
      boolean found = false; 
      while(lo<hi){ 
       if(lo==i){ 
        lo++; 
        continue; 
       } 
       if(hi==i){ 
        hi--; 
        continue; 
       } 
       int val = arr[lo] + arr[hi] + arr[i]; 
       if(val == req){ 
        System.out.println(arr[lo] + " + " + arr[hi] + " + " + arr[i] + " = " + req); 
        found = true; 
        break; 
       }else if(val < req){ 
        lo++; 
       }else{ 
        hi--; 
       } 
      } 
      if(found)break; 
     } 
    } 

Answer 3

In teoria computazionale, questo è noto come 3sum problema. La migliore soluzione per questo problema trovata finora costa O (N^2). È ancora una questione aperta se questo può essere risolto con un costo migliore. È possibile trovare un'implementazione di questo algoritmo here.

Answer 4

Se k è circa uguale alla dimensione dell'array (o inferiore) e tutti i numeri sono positivi (occuparsi di zeri è banale), è possibile utilizzare DP in modo efficiente. Per tutti i numeri da 0 a k, si ricorda se è possibile ottenere utilizzando zero, uno, due o tre numeri interi dalla matrice. La soluzione è O(Nk) in tempo e O(k) nello spazio ed è molto facile da implementare.

int[] myarray = {1, 2, 3, 4, 5, 6}; 
int k = 14; 

int[] dp = new int[k+1]; 
dp[0] = 1; 
for (int i = 0; i < myarray.length; ++i) { 
    for (int j = k; j >= myarray[i]; --j) { 
     dp[j] |= dp[j-myarray[i]] << 1; 
    } 
} 
if ((dp[k] & 8) > 0) { 
    System.out.println("YES"); 
} else { 
    System.out.println("NO"); 
}