Comment écrire un algorithme permettant de vérifier si la somme de deux nombres dans un tableau/liste correspond à un nombre donné?

Je suis sûr qu'il ya une meilleure façon, mais voici une idée:

1. Tri un tableau
2. Pour chaque élément e dans la matrice binaire de recherche pour le complément (somme - e)

Ces deux opérations sont O(n log n).

Utiliser un table de hachage. Insérez chaque numéro dans votre table de hachage, avec son index. Alors, laissez S être votre somme désirée. Pour chaque nombre array[i] dans votre premier tableau, voir si S - array[i] existe dans votre table de hachage avec un indice différent de i.

Moyenne des cas est O(n), dans le pire des cas est O(n^2), afin d'utiliser les binaires de recherche de la solution si vous avez peur de le pire des cas.

C'est en Java : Ce même supprime les doublons éventuels.. Runtime - O(n^2)

private static int[] intArray = {15,5,10,20,25,30};
private static int sum = 35;

private static void algorithm()
{
    Map<Integer, Integer> intMap = new Hashtable<Integer, Integer>();
    for (int i=0; i<intArray.length; i++) 
    {
        intMap.put(i, intArray[i]);
        if(intMap.containsValue(sum - intArray[i]))
            System.out.println("Found numbers : "+intArray[i] +" and "+(sum - intArray[i]));

    }
    System.out.println(intMap);
}

Voici un essai en C. Ce n'est pas marquée devoirs.

//Assumes a sorted integer array with no duplicates
void printMatching(int array[], int size, int sum)
{
   int i = 0, k = size - 1;
   int curSum;
   while(i < k)
   {
      curSum = array[i] + array[k];
      if(curSum == sum)
      {
         printf("Found match at indices %d, %d\n", i, k);
         i++;k--;
      }
      else if(curSum < sum)
      {
         i++;
      }
      else
      {
         k--;
      }
   }
}

Voici quelques test de sortie à l'aide de int a[] = { 3, 5, 6, 7, 8, 9, 13, 15, 17 };

Searching for 12..
Found match at indices 0, 5
Found match at indices 1, 3
Searching for 22...
Found match at indices 1, 8
Found match at indices 3, 7
Found match at indices 5, 6
Searching for 4..
Searching for 50..

La recherche est linéaire, donc O(n). Le genre de ce qui se passe derrière les scènes, c'est d'aller à O(n*logn) si vous utilisez l'un des bons sortes.

Parce que les mathématiques derrière Big-O, le plus petit terme additif conditions efficacement le décrochage de votre calcul, et vous vous retrouvez avec O(n logn).

Voici un algorithme qui s'exécute en O(n) si le tableau est déjà trié ou O(n log n) si ce n'est pas déjà triées. Prend des repères de beaucoup d'autres réponses ici. Le Code est en Java, mais ici, c'est un pseudo-code de la dérivée de nombreuses réponses, mais optimisé pour les doublons généralement

1. La chance de deviner si le premier et le dernier éléments sont égaux à la cible
2. Créer une Carte avec une valeur actuelle et de ses occurrences
3. Créer une visité Ensemble qui contient des éléments nous l'avons déjà vu, cela permet d'optimiser les doublons, tels que dire à une entrée de (1,1,1,1,1,1,2) et de la cible 4, nous ne jamais calculer le 0 et le dernier élément, et pas toutes les 1 dans le tableau.

4. Utiliser ces variables pour calculer l'existence de la cible dans le tableau;
   définir la currentValue à la matrice[ith];
   ensemble newTarget à la cible de currentValue;
   ensemble expectedCount 2 si currentValue est égal à newTarget ou 1 dans le cas contraire

   ET renvoyer true seulement si
   un. nous n'avons jamais vu cet entier avant ET
   b. nous avons une certaine valeur pour la newTarget dans la carte que nous avons créé
   c. et le comte de la newTarget est égale ou supérieure à la expectedCount

AUTREMENT
répétez l'étape 4 jusqu'à ce que nous arrivent en fin de tableau et renvoie la valeur false SINON;

Comme je l'ai mentionné à la meilleure utilisation possible pour une visité magasin c'est quand nous avons des doublons, il n'y aurait jamais de l'aide si aucun des éléments sont des doublons.

Code Java à https://gist.github.com/eded5dbcee737390acb4

Étape 1 : Trier le tableau en O(n logn)

Étape 2 : Trouver deux indices

0<=i<j<=n dans[0..n] tel que a[i]+a[j]==k, où k est la clé donnée.

int i=0,j=n;
while(i<j) {
   int sum = a[i]+a[j];
   if(sum == k)
        print(i,j)
   else if (sum < k)
        i++;
   else if (sum > k)
        j--;
}

1. Résolu la question en Swift 4.0
2. Résolu de 3 façons différentes (avec 2 différents type de retour -> Boolean et Index)

A) TimeComplexity => 0(n Log n) SpaceComplexity => 0(n).

B) TimeComplexity => 0(n^2) SpaceComplexity => 0(1).

C) TimeComplexity => 0(n) SpaceComplexity => 0(n)

1. Choisir la Solution A, B ou C selon le Compromis.

   //***********************Solution A*********************//
   //This solution returns TRUE if any such two pairs exist in the array
   func binarySearch(list: [Int], key: Int, start: Int, end: Int) -> Int? { //Helper Function
   
               if end < start {
                   return -1
               } else {
                   let midIndex = (start + end) /2
   
                   if list[midIndex] > key {
                       return binarySearch(list: list, key: key, start: start, end:  midIndex - 1)
                   } else if list[midIndex] < key {
                       return binarySearch(list: list, key: key, start: midIndex + 1, end: end)
                   } else {
                       return midIndex
                   }
               }
           }
   
           func twoPairSum(sum : Int, inputArray: [Int]) -> Bool {
   
               //Do this only if array isn't Sorted!
               let sortedArray = inputArray.sorted()
   
               for (currentIndex, value)  in sortedArray.enumerated() {
                   if let indexReturned =  binarySearch(list: sortedArray, key: sum - value, start: 0, end: sortedArray.count-1) {
                       if indexReturned != -1 && (indexReturned != currentIndex) {
                           return true
                       }
                   }
               }
               return false
           }
   
    //***********************Solution B*********************//
    //This solution returns the indexes of the two pair elements if any such two pairs exists in the array
    func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] {
   
               for currentIndex in 0..<nums.count {
                   for nextIndex in currentIndex+1..<nums.count {
                       if calculateSum(firstElement: nums[currentIndex], secondElement: nums[nextIndex], target: target) {
                           return [currentIndex, nextIndex]
                       }
                   }
               }
   
               return []
           }
   
           func calculateSum (firstElement: Int, secondElement: Int, target: Int) -> Bool {//Helper Function
               return (firstElement + secondElement) == target
           }
   
       //*******************Solution C*********************//
      //This solution returns the indexes of the two pair elements if any such two pairs exists in the array
      func twoPairSum(_ nums: [Int], _ target: Int) -> [Int] {
   
               var dict = [Int: Int]()
   
               for (index, value) in nums.enumerated() {
                   dict[value] = index
               }
   
               for (index, value) in nums.enumerated() {
                   let otherIndex = dict[(target - value)]
                   if otherIndex != nil && otherIndex != index {
                       return [index, otherIndex!]
                   }
               }
   
               return []
           }