trouver un triplet ayant une somme donnée

Question

J'ai lutté avec ces questions depuis un certain temps maintenant. La question est la suivante: -

Nous avons n^2 nombres. Nous avons besoin de savoir s'il existe un triplet a, b, c tel que a + b + c = 0. Pour un cas plus générique, a + b + c = k. (k est donné)

Il existe une solution avec une complexité O (n^2log (n)).

Toute aide serait grandement appréciée.

grâce

Answer 1

Voir si this aide.

Answer 2

Pour obtenir ceci dans O (n²logn), vous devez trier les nombres. Trouvez toutes les combinaisons de 2 nombres, et faites une recherche binaire pour trouver la troisième.

La limite supérieure est beaucoup plus élevée pour la version générale du problème.

Answer 3

J'ai écrit une solution approximative.

On peut certainement le faire en O (n^2). Vous n'avez pas à trier cela.

C'est une extension du problème qui nécessite de sommer deux nombres en x et l'astuce consiste à utiliser la table de hachage.

def triplets(l, total): 
    """Sum of 3 numbers to get to total 
    Basically an extension of the 2 table 
    """ 
    l = set(l) 
    d = { } 

    for i in l: 
     remain = total - i 

     inside = {} 
     for j in l: 
      if i == j: 
       continue 
      inside[j] = remain -j 

     d[i] = inside 

    good = set() 

    for first, dic in d.iteritems(): 
     for second, third in dic.iteritems(): 
      if third in l: 
       good.add(tuple(sorted([first, second, third]))) 

    for each in good: 
     print each 

triplets([2, 3, 4, 5, 6], 3+4+5) 

NOTE: nous pouvons utiliser une méthode de tri rapide pour les triplets qui seront O (1).