Trouver 2 nombres dans un tableau non trié égal à une somme donnée

Question

Nous avons besoin de trouver la paire de nombres dans un tableau dont la somme est égale à une valeur donnée.

A = {6,4,5,7,9,1,2}

Somme = 10 Ensuite, les paires sont - {6,4} , {9,1}

J'ai deux solutions pour cela .

• un O(nlogn) solution de tri + somme de contrôle avec 2 itérateurs (début et fin).
• un O(n) solutiin - le hachage de la matrice. Puis de vérifier si sum-hash[i] existe dans la table de hachage ou pas.

Mais , le problème est que, bien que la deuxième solution est de O(n) le temps , mais utilise O(n) de l'espace.

Donc , je me demandais si nous pourrions le faire en O(n) en temps et O(1) de l'espace. Et ce n'est PAS de devoirs!

Answer 1

Utilisation sur place radix de tri et de l'OP de la première solution avec 2 itérateurs, venant les uns envers les autres.

Si les chiffres dans le tableau ne sont pas une sorte de multi-précision des numéros et sont, par exemple, les nombres entiers de 32 bits, vous pouvez les trier en 2*32 passes en utilisant pratiquement pas d'espace supplémentaire (1 bit par passe). Ou 2*8 passes et 16 entier compteurs (4 bits par passe).

---

Détails pour le 2 itérateurs solution:

Première itérateur qui pointe sur le premier élément du tableau trié et les progrès de l'avant. Deuxième itérateur pointe sur le dernier élément du tableau et les progrès vers l'arrière.

Si la somme des éléments, référencé par les itérateurs, est inférieure à la valeur requise, l'avance de la première itérateur. Si elle est supérieure à la valeur requise, l'avance, la deuxième itérateur. Si elle est égale à la valeur requise, le succès.

Un seul passage est nécessaire, donc le temps de la complexité est O(n). L'espace de la complexité est O(1). Si radix sort est utilisé, les complexités de l'ensemble de l'algorithme sont les mêmes.

---

Si vous êtes intéressé par les problèmes liés (avec une somme de plus de 2 numéros), voir "Somme de sous-ensemble fixe de taille du sous-ensemble" et de "Trouver trois éléments dans un tableau dont la somme est plus proche d'un nombre donné".

Answer 2

C'est un classique de la question de l'entrevue de Microsoft research Asia.
Comment Trouver 2 nombres dans un tableau non trié égal à une somme donnée.

[1]la force brute de la solution
Cet algorithme est très simple. Le temps de la complexité est O(N^2)

[2]à l'Aide de la recherche binaire
À l'aide de bianry à la recherche de la Somme-arr[i] avec tous les arr[i], Le temps de la complexité peut être réduite à O(N*logN)

[3]À L'Aide De Hachage
De Base [2] de l'algorithme et de l'utilisation de hachage, le temps de la complexité peut être réduite à O(N), mais cette solution permettra d'ajouter le O(N) l'espace de hachage.

[4]algorithme Optimal:

Pseduo-code:

for(i=0;j=n-1;i<j)
   if(arr[i]+arr[j]==sum) return (i,j);
else if(arr[i]+arr[j]<sum) i++;
else j--;
return(-1,-1);

ou

If a[M] + a[m] > I then M--
If a[M] + a[m] < I then m++
If a[M] + a[m] == I you have found it
If m > M, no such numbers exist.

Et c'Est en quesiton complètement résolu? Pas de. Si le nombre est N. Ce problème va devenir très complexe.

La quesiton alors:
Comment puis-je trouver toutes les combinaison des cas, avec un nombre donné?

C'est un classique NP-Complets problème qui est appelé sous-ensemble-somme.
Pour comprendre NP/NPC/NP-Difficile vous feriez mieux de lire quelques livres professionnels.

Références:
[1]http://www.quora.com/Mathematics/How-can-I-find-all-the-combination-cases-with-a-given-number
[2]http://en.wikipedia.org/wiki/Subset_sum_problem

Answer 3

for (int i=0; i < array.size(); i++){
  int value = array[i];
  int diff = sum - value; 
  if (! hashSet.contains(diffvalue)){
      hashSet.put(value,value);
  } else{
       printf(sum = diffvalue + hashSet.get(diffvalue));
  } 
}

--------
Sum being sum of 2 numbers.

Answer 4

Si l'on suppose que la valeur M pour qui les paires sont suppose de somme est constante et que les entrées dans le tableau sont positifs, alors vous pouvez le faire en un seul passage (O(n) du temps) à l'aide d' M/2 des pointeurs (O(1) de l'espace) comme suit. Les pointeurs sont étiquetés P1,P2,...,Pk où k=floor(M/2). Puis faire quelque chose comme ceci

for (int i=0; i<N; ++i) {
  int j = array[i];
  if (j < M/2) {
    if (Pj == 0)
      Pj = -(i+1);   // found smaller unpaired
    else if (Pj > 0)
      print(Pj-1,i); // found a pair
      Pj = 0;
  } else
    if (Pj == 0)
      Pj = (i+1);    // found larger unpaired
    else if (Pj < 0)
      print(Pj-1,i); // found a pair
      Pj = 0;
  }
}

Vous pouvez gérer les entrées répétées (p. 6) en stockant les indices de chiffres en base N, par exemple. Pour M/2, vous pouvez ajouter le conditionnel

  if (j == M/2) {
    if (Pj == 0)
      Pj = i+1;      // found unpaired middle
    else
      print(Pj-1,i); // found a pair
      Pj = 0;
  } 

Mais maintenant vous avez le problème de mettre les paires ensemble.

Answer 5

La solution évidente ne fonctionne-t-elle pas (itérer sur chaque paire consécutive) ou les deux nombres sont-ils dans un ordre quelconque?

Dans ce cas, vous pouvez trier la liste des nombres et utiliser un échantillonnage aléatoire pour la partitionner jusqu'à obtenir une sous-liste suffisamment petite pour être itérée.