Trouvez une paire d'éléments d'un tableau dont la somme est égale à un nombre donné.

Question

Étant donné un tableau de n nombres entiers et un nombre X, trouvez toutes les paires uniques d'éléments (a,b), dont la somme est égale à X.

La solution suivante est ma solution, elle est O(nLog(n)+n), mais je ne suis pas sûr qu'elle soit optimale ou non.

int main(void)
{
    int arr [10] = {1,2,3,4,5,6,7,8,9,0};
    findpair(arr, 10, 7);
}
void findpair(int arr[], int len, int sum)
{
    std::sort(arr, arr+len);
    int i = 0;
    int j = len -1;
    while( i < j){
        while((arr[i] + arr[j]) <= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            i++;
        }
        j--;
        while((arr[i] + arr[j]) >= sum && i < j)
        {
            if((arr[i] + arr[j]) == sum)
                cout << "(" << arr[i] << "," << arr[j] << ")" << endl;
            j--;
        }
    }
}

Answer 1

Il existe trois approches pour cette solution :

Soit la somme T et n la taille du tableau.

Approche 1 :
La façon naïve de procéder serait de vérifier toutes les combinaisons (n choisit 2). Cette recherche exhaustive est O(n 2 ).

Approche 2 :
 Un meilleur moyen serait de trier le tableau. Cela prend O(n log n)
Alors pour chaque x dans le tableau A, utilisez la recherche binaire pour trouver T-x. Cela prendra O(nlogn).
Ainsi, la recherche globale est O(n log n)

Approche 3 :
Le meilleur moyen serait d'insérer chaque élément dans une table de hachage (sans tri). Cela prend O(n) comme temps constant d'insertion.
Alors pour chaque x, on peut juste chercher son complément, T-x, qui est O(1).
Globalement, le temps d'exécution de cette approche est de O(n).

Vous pouvez consulter plus ici Merci.

Answer 2

# Let arr be the given array.
# And K be the give sum

for i=0 to arr.length - 1 do
  # key is the element and value is its index.
  hash(arr[i]) = i  
end-for

for i=0 to arr.length - 1 do
  # if K-th element exists and it's different then we found a pair
  if hash(K - arr[i]) != i  
    print "pair i , hash(K - arr[i]) has sum K"
  end-if
end-for

Answer 3

Mise en œuvre en Java : Utilisation de l'algorithme de Codaddict (Peut-être légèrement différent)

import java.util.HashMap;

public class ArrayPairSum {

public static void main(String[] args) {        

    int []a = {2,45,7,3,5,1,8,9};
    printSumPairs(a,10);        

}

public static void printSumPairs(int []input, int k){
    Map<Integer, Integer> pairs = new HashMap<Integer, Integer>();

    for(int i=0;i<input.length;i++){

        if(pairs.containsKey(input[i]))
            System.out.println(input[i] +", "+ pairs.get(input[i]));
        else
            pairs.put(k-input[i], input[i]);
    }

}
}

Pour l'entrée = {2,45,7,3,5,1,8,9} et si Sum est 10

Paires de sorties :

3,7 
8,2
9,1

Quelques remarques sur la solution :

• Nous itérons une seule fois dans le tableau --> temps O(n)
• Le temps d'insertion et de consultation dans le hachage est de O(1).
• Le temps global est O(n), bien qu'il utilise un espace supplémentaire en termes de hachage.

Answer 4

Implémentation de Python :

import itertools
list = [1, 1, 2, 3, 4, 5,]
uniquelist = set(list)
targetsum = 5
for n in itertools.combinations(uniquelist, 2):
    if n[0] + n[1] == targetsum:
        print str(n[0]) + " + " + str(n[1])

Sortie :

1 + 4
2 + 3

Answer 5

Voici une solution qui tient compte des doublons. Elle est écrite en javascript et suppose que le tableau est trié. La solution s'exécute en temps O(n) et n'utilise pas de mémoire supplémentaire en dehors de la variable.

var count_pairs = function(_arr,x) {
  if(!x) x = 0;
  var pairs = 0;
  var i = 0;
  var k = _arr.length-1;
  if((k+1)<2) return pairs;
  var halfX = x/2; 
  while(i<k) {
    var curK = _arr[k];
    var curI = _arr[i];
    var pairsThisLoop = 0;
    if(curK+curI==x) {
      // if midpoint and equal find combinations
      if(curK==curI) {
        var comb = 1;
        while(--k>=i) pairs+=(comb++);
        break;
      }
      // count pair and k duplicates
      pairsThisLoop++;
      while(_arr[--k]==curK) pairsThisLoop++;
      // add k side pairs to running total for every i side pair found
      pairs+=pairsThisLoop;
      while(_arr[++i]==curI) pairs+=pairsThisLoop;
    } else {
      // if we are at a mid point
      if(curK==curI) break;
      var distK = Math.abs(halfX-curK);
      var distI = Math.abs(halfX-curI);
      if(distI > distK) while(_arr[++i]==curI);
      else while(_arr[--k]==curK);
    }
  }
  return pairs;
}

J'ai résolu ce problème lors d'un entretien pour une grande entreprise. Ils l'ont pris mais pas moi. Alors le voici pour tout le monde.

Commencez par les deux côtés du tableau et progressez lentement vers l'intérieur en vous assurant de compter les doublons s'ils existent.

Il ne compte que les paires mais peut être retravaillé pour

• trouver les paires
• trouver des paires < x
• trouver des paires > x

Profitez-en !