Algorithme permettant de trouver la paire de nombres dans un tableau d'entiers dont la somme est égale

Question

Algorithme permettant de trouver la paire de nombres dans un tableau d'entiers dont la somme est égale. ex {1 2 3 4 6}

ici {3 2} {4 1} devrait être la sortie, car la somme est 3 + 2 = 5, 4 + 1 = 5.

Ici, l'essentiel est la complexité qui doit être O (n). S'il vous plaît aidez-moi si nous trouvons des solutions pour cela?

Answer 1

Etes-vous sûr que le problème peut être résolu dans O (n)? Imaginez le cas où la séquence d'entrée est juste {0, 0, 0, 0, 0, 0, ..., 0}. Ici, chaque paire satisfait la condition. La simple énumération de toutes les paires est déjà au moins O (n^2).

Answer 2

Je ne suis pas sûr que ce soit possible de faire efficacement. Selon les informations fournies, le tableau n'est pas trié et vous ne connaissez pas la sommation attendue que vous devrez parcourir deux fois dans le tableau.

Pensez à un algorithme de recherche. le moins complexe, la recherche linéaire (séquentielle) a la complexité O (n). C'est juste pour traverser le tableau. Si vous connaissez la somme que vous attendez, le cas est similaire, et ce que vous devez faire est une recherche linéaire. Pour toute autre chose, vous obtenez une plus grande complexité.

Mais dans votre cas, vous ne connaissez pas la somme, vous devrez donc traverser plus d'une fois. Ma tête dit que c'est O (n log n) ou O (n^2).

Peut-être qu'il pourrait y avoir une solution qui utilise plus de structures de données, peut-être une table de sommation (tableau 2D ???) mais le risque d'exister une telle solution est faible.

Answer 3

Je pense qu'il est possible:

vous avez besoin d'un deuxième réseau tmp = {} avec la longueur de somme.

sum = 5 
array = {1,2,3,4,6} 
for every i in array{ 
    if i>=sum: 
     continue 
    if tmp[i] != 0 { 
     output {i,(sum-i)} 
     tmp[i] = 0 
     continue 
    } 

    tmp[sum-i] := i 
} 

c'est tout. si simple et O (n)

contre:

1. il ne trouvera pas une paire comme {} 5,0, donc vous devez utiliser de véritables integer-objets pour vérifier à la ligne 6 contre NULL et affecter NULL dans la ligne 8,
2. paires avec un nombre négatif ne fonctionnera pas.

Answer 4

Le problème, comme indiqué, semble manquer certaines contraintes qui seraient utiles. Le premier que je voudrais suggérer, chaque entier du tableau devrait être distinct. À tout le moins, la sortie devrait être de paires uniques.

Une autre contrainte qui peut ou ne peut pas s'appliquer à un domaine de problème spécifique est un tableau trié. Cette contrainte, lorsqu'elle est vraie, suggère un algorithme simple. Démarrer 2 pointeurs, à gauche et à droite, leurs extrémités respectives. Si la somme correspond, la sortir, incrémenter à gauche et décrémenter à droite. Si ce n'est pas le cas, décrémentez le pointeur de droite si la somme est trop grande ou augmentez la gauche (trop petite). Continuez à ajuster à gauche et à droite jusqu'à ce qu'ils se croisent quelque part au milieu.

Pour un tableau non trié. Créez une table de hachage, insérez tous les entiers. Parcourez à nouveau le tableau, cette fois-ci, recherchez la valeur dans la table de hachage pour satisfaire la somme requise. Si la fonction de hachage est parfaite (ce qui peut être difficile à réaliser), alors l'exécution attendue est O (n).