Vérification si 2 numéros de tableau s'ajoutent à i

O(n) time and O(1) space
If the array is sorted there is a solution in O(n) time complexity.Suppose are array is
    array = {0, 1, 3, 5, 8, 10, 14}And our x1 + x2 = k = 13, so output should be= 5, 8
Take two pointers one at start of array, one at end of array
Add both the elements at ptr1 and ptr2
    array[ptr1] + array[ptr2]


if sum > k then decrement ptr2 else increment ptr1

Repeat step2 and step3 till ptr1 != ptr2
Same thing explained in detail here. Seems like an Amazon interview Question
http://inder-gnu.blogspot.com/2007/10/find-two-nos-in-array-whose-sum-x.html

public static boolean findSum2(int[] a, int sum) {
        if (a.length == 0) {
            return false;
        }
        Arrays.sort(a);


        int i = 0;
        int j = a.length - 1;
        while (i < j) {
            int tmp = a[i] + a[j];
            if (tmp == sum) {
                System.out.println(a[i] + "+" + a[j] + "=" + sum);
                return true;
            } else if (tmp > sum) {
                j--;
            } else {
                i++;
            }
        }
        return false;
}

Cela pourrait être possible de la manière suivante: Avant de mettre les éléments dans le hashmap, vous pouvez vérifier si l'élément est supérieur à la somme requise. Si tel est le cas, vous pouvez simplement ignorer cet élément, sinon vous pouvez continuer à la mettre dans le hashmap. C'est une légère amélioration de votre algorithme, bien que le temps total reste toujours le même.

Ceci peut être résolu à l'aide de l'algorithme de l'Union-Trouver, qui peut vérifier en temps constant si un élément est dans un ensemble.

Donc, l'algorithme serait donc: P>

foundsum0 = false;
foreach (el: array) {
    if find (-x): foundsum0 = true;
    else union (x);
}

Voici une solution O (n) en Java en utilisant O (n) espace supplémentaire. Cela utilise hashset pour la mettre en œuvre

http://www.dsalgo.com/unsortedtwosumtok.php

Voici une solution Sorcière prend en compte les entrées en double. Il est écrit en JavaScript et suppose que la matrice est triée. La solution s'exécute dans O (n) temps et n'utilise aucune mémoire supplémentaire à partir de variables. Choisissez un algorithme de tri de choix. (RADIX O (kN)!) puis exécutez le tableau à travers ce bébé.

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;
}

• Trouvez les paires li>
• Trouvez des paires
• Trouver des paires> x li> ul>

  Profitez et n'oubliez pas de bump si sa meilleure solution! p> p>

diviser le tableau en deux groupes <= i / 2 et> i / 2. Puis divisez-les en <= i / 4,> i / 4 et <= 3i / 4,> 3i / 4 Et répéter pour le journal (i) étapes et vérifiez les paires de jointures de l'extérieur E.g 1i / 8 <= et> 7i / 8 et si elles contiennent tous les deux au moins un élément, ils ajoutent à I. Cela prendra n.log (i) + n / 2 étapes et pour i

Une implémentation dans Python xxx

entrée: La liste est une liste de chiffres (A dans la question ci-dessus) ...
k est la somme (i dans la question ci-dessus) ....

Les sorties de la fonction true s'il existe une paire dans la liste dont la somme est égale à k et False sinon ...

J'utilise un dictionnaire dont la clé est l'élément de la matrice (liste) et la valeur est le nombre de ce élément (nombre de fois que cet élément est présent dans cette liste). La complexité moyenne du temps d'exécution est O (n).

Cette implémentation prend également en charge deux cas de bord importants:

• Numéros répétés dans la liste et
• ne pas ajouter le même numéro deux fois.