Trouver toutes les paires d'entiers dans un tableau qui résume à une valeur spécifiée

Je ne vois pas pourquoi l'approche de la table de hachage est inefficace, au moins en termes d'analyse d'algorithme - en termes de localité de mémoire, certes, cela peut être assez mauvais. Quoi qu'il en soit, scannez le tableau deux fois...

Première analyse-mettre tous les éléments du tableau dans la table de hachage-O (N) total. Les inserts individuels ne sont amortis que O (1), mais une chose intéressante sur le fonctionnement de l'analyse amortie signifie que le O(n) est absolu - pas amorti.

Deuxième scan - vérifier (somme - courant) dans la table de hachage - O(n) total.

Cela bat les méthodes de tri et de recherche O(N log n), du moins en théorie.

Ensuite, notez que vous pouvez combiner les deux analyses en une seule. Vous pouvez repérer une paire dès que vous rencontrez le deuxième de cette paire lors de la première analyse. En pseudo-code...

for i in array.range
  hashset.insert (array [i])

  diff = sum - array [i]
  if hashset.includes (diff)
    output diff, array [i]

Si vous avez besoin de positions des éléments, utilisez un hashmap et stockez-y les positions des éléments. Si vous avez besoin de faire face aux doublons, vous devrez peut-être stocker des comptes dans un hashmap. Pour les postes et les doublons, vous pourriez avoir besoin d'un hashmap de pointeurs de départ pour les listes de positions liées.

Cela fait des hypothèses sur l'implémentation de la table de hachage, mais assez sûres étant donné les implémentations habituelles dans la plupart des langages et bibliothèques actuels.

BTW-la combinaison des analyses ne doit pas être considérée comme une optimisation. La surcharge d'itération devrait être insignifiante. Les problèmes de localité de mémoire pourraient rendre un seul passage légèrement plus efficace pour les très grands tableaux, mais les vrais problèmes de localité de mémoire seront dans le Hashtable recherches de toute façon.

IMO la seule vraie raison de combiner les scans est parce que vous voulez seulement que chaque paire soit signalée une fois que dans une approche à deux scans, ce serait un peu plus compliqué.

1. Si le tableau est trié:

   Let i = 0, j = fin du tableau, sum = la valeur que vous recherchez, alors faites:

   Si i + J = somme, alors sortie (i, j).
   Si i + j Si i + j > somme, déplacez j vers la gauche.

   Complexité temporelle: O (n). L'espace de la complexité: O(1).

2. Si le tableau n'est pas trié, il existe quelques façons d'aborder cette problème:

   1. Triez le tableau, puis utilisez l'approche ci-dessus.

   2. HashMap:

      Stocke tous les éléments dans un HashMap.

      a+b=sum, donc b=sum-a. Pour chaque élément a du tableau, recherchez b à partir du HashMap.

      HashMap Lookup prend amorti O (1).

      Complexité temporelle: O (n). L'espace de la complexité: O(n).

   3. BitMap:

      Parcourir l'entrée pour créer un bitmap où chaque bit correspond à une valeur d'élément. Disons que l'entrée est {2,5,8}, puis nous basculons les indices 2, 5 et 8 du tableau bitmap du binaire 0 à 1. Cela prend O(1) par élément, donc O(n) au total.

      Passez à nouveau par l'entrée. Nous connaissons b=sum-a, donc pour chaque élément a dans l'entrée, recherchez son b, ce qui peut être fait dans O(1) puisque c'est un index bitmap. Cela prend également O (n) au total.

      Complexité temporelle: O (n) + O(N) = O (n). Complexité de l'Espace: Espace bitmap = O (n).

Vous n'avez même pas besoin de stocker tous les éléments dans hashmap, puis de numériser. Vous pouvez analyser pendant la première itération elle-même.

void foo(int[] A, int sum) {
    HashSet<Integer> set = new HashSet<Integer>();
    for (int e : A) {
        if (set.contains(sum-e)) {
            System.out.println(e + "," + (sum-e));
            // deal with the duplicated case
            set.remove(sum-e);
        } else {
            set.add(e);
        }
    }
}

Que diriez-vous de trier le tableau, puis de marcher des deux extrémités?

Si cela ne vous dérange pas de dépenser O(M) dans l'espace, où M est la somme que vous cherchez, vous pouvez le faire en O(N + M) temps. Set sums[i] = 1 lorsque i <= M sur un seul passage sur N, puis vérifier (sums[i] && sums[M-i]) sur un seul passage sur M/2.

#include <iostream>
using namespace std;

#define MAX 15

int main()
{
 int array[MAX] = {-12,-6,-4,-2,0,1,2,4,6,7,8,12,13,20,24};
 const int find_sum = 0;
 int max_index = MAX - 1;
 int min_index = 0;
 while(min_index < max_index)
 {
  if(array[min_index] + array[max_index-min_index] == find_sum)
  {
   cout << array[min_index] << " & " << array[max_index-min_index] << " Matched" << endl;
   return 0;
  }
  if(array[min_index]+array[max_index-min_index] < find_sum)
  {
   min_index++;
   //max_index++;
  }
  if(array[min_index]+array[max_index-min_index] > find_sum)
  {
   max_index--;
  }
 }
 cout << "NO MATCH" << endl;
 return 0;
}
//-12 & 12 matched

Implémenté en python 2.7:

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

Voici une solution qui prend en compte les entrées en double. Il est écrit en javascript et suppose que array est trié. La solution s'exécute en temps O (N) et n'utilise aucune mémoire supplémentaire en dehors de 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;
}

Alors voilà pour tout le monde.

Commencez par les deux côtés du tableau et travaillez 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é à

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

Profitez et n'oubliez pas de le cogner si c'est la meilleure réponse!!

Une solution qui prend en compte les doublons et utilise chaque Nombre une seule fois:

void printPairs(int[] numbers, int S) {
    // toMap(numbers) converts the numbers array to a map, where
    // Key is a number from the original array
    // Value is a count of occurrences of this number in the array
    Map<Integer, Integer> numbersMap = toMap(numbers); 

    for (Entry<Integer, Integer> entry : numbersMap.entrySet()) {
      if (entry.getValue().equals(0)) {
        continue;
      }
      int number = entry.getKey();
      int complement = S - number;
      if (numbersMap.containsKey(complement) && numbersMap.get(complement) > 0) {
      for (int j = 0; j < min(numbersMap.get(number), 
                              numbersMap.get(complement)); j++) {
        if (number.equals(complement) && numbersMap.get(number) < 2) {
           break;
        }
        System.out.println(number, complement);
        numbersMap.put(number, numbersMap.get(number) - 1);
        numbersMap.put(complement, numbersMap.get(complement) - 1);
      }
    }
  }
}

Solution Hashtable, en Ruby (assez simple à comprendre):

value = 100
pairs = [1,99,5,95]
hash_of_pairs = {}

pairs.map! do |pair|
  # Adds to hashtable the pair
  hash_of_pairs[pair] = pair

  # Finds the value the pair needs
  new_pair = hash_of_pairs[value - pair]

  # Returns the pair whenever the pair exists, or nil
  [new_pair, pair] if !new_pair.nil?
end.compact! # Cleans up the array, removing all nil values

print pairs # [[1,99], [5,95]]

Nous pouvons utiliser la carte C++ STL pour résoudre ce problème

void subsetSum(int arr[], int n, int sum)
{
    map<int, int>Map;

    for(int i=0; i<n; i++)
    {
        Map[arr[i]]++;
        if(Map.count(sum-arr[i]))
        {
            cout<<arr[i]<<" "<<sum-arr[i]<<"\n";
        }
    }
}

@Test
public void hasPairWithSum() {
  assertFalse(hasPairWithSum_Ordered_Logarithmic(new int[] { 1, 2, 3, 9 }, 8));
  assertTrue(hasPairWithSum_Ordered_Logarithmic(new int[] { 1, 2, 4, 4 }, 8));

  assertFalse(hasPairWithSum_Ordered_Linear(new int[] { 1, 2, 3, 9 }, 8));
  assertTrue(hasPairWithSum_Ordered_Linear(new int[] { 1, 2, 4, 4 }, 8));

  assertFalse(hasPairWithSum_Unsorted_Linear(new int[] { 9, 1, 3, 2 }, 8));
  assertTrue(hasPairWithSum_Unsorted_Linear(new int[] { 4, 2, 1, 4 }, 8));

  assertFalse(hasPairWithSum_Unsorted_Quadratic(new int[] { 9, 1, 3, 2 }, 8));
  assertTrue(hasPairWithSum_Unsorted_Quadratic(new int[] { 4, 2, 1, 4 }, 8));
}

private boolean hasPairWithSum_Ordered_Logarithmic(int[] data, int sum) {
  for (int i = 0; i < data.length; i++) {
    int current = data[i];
    int complement = sum - current;
    int foundIndex = Arrays.binarySearch(data, complement);
    if (foundIndex >= 0 && foundIndex != i) {
      return true;
    }
  }
  return false;
}

private boolean hasPairWithSum_Ordered_Linear(int[] data, int sum) {
  int low = 0;
  int high = data.length - 1;
  while (low < high) {
    int total = data[low] + data[high];
    if (total == sum) {
      return true;
    } else if (total < sum) {
      low++;
    } else {
      high--;
    }
  }
  return false;
}

private boolean hasPairWithSum_Unsorted_Linear(int[] data, int sum) {
  Set<Integer> complements = Sets.newHashSet();
  for (int current : data) {
    if (complements.contains(current)) {
      return true;
    }
    complements.add(sum - current);
  }
  return false;
}

private boolean hasPairWithSum_Unsorted_Quadratic(int[] data, int sum) {
  for (int i = 0; i < data.length; i++) {
    int current = data[i];
    int complement = sum - current;
    for (int j = 0; j < data.length; j++) {
      if (data[j] == complement && i != j) {
        return true;
      }
    }
  }
  return false;
}

Création d'une table de hachage, puis recherche de valeur.

function sum_exist(num : number, arr : any[]) {
    var number_seen = {};
    for(let item of arr){
        if(num - item in number_seen){
            return true
        }
        number_seen[item] = 0;
    }
    return false;
}

Cas de Test (en utilisant Jest)

test('Given a list of numbers, return whether any two sums equal to the set number.', () => {
    expect(sum_exist(17 , [10, 15, 3, 7])).toEqual(true);
});


test('Given a list of numbers, return whether any two sums equal to the set number.', () => {
    expect(sum_exist(16 , [10, 15, 3, 7])).toEqual(false);
});