trouver quatre éléments dans la gamme dont la somme est égale à un nombre donné X

Vous pouvez le faire en O(n^2). Fonctionne très bien avec dupliqué et les nombres négatifs.

modifier comme André l'a noté dans le commentaire, le temps est avec l'utilisation de hachage, qui a "pire des cas" (même si il est moins probable que de gagner au loto). Mais vous pouvez également remplacer la table de hachage de l'équilibre de l'arbre (TreeMap en java) et d'obtenir la garantie stable O(n^2 * log(n)) de la solution.

Hashtable sums sera possible de stocker toutes les sommes de deux éléments différents. Pour chaque somme S il renvoie la paire d'indices i et j tels que a[i] + a[j] == S et i != j. Mais au départ, c'est vide, nous allons le remplir sur le chemin.

for (int i = 0; i < n; ++i) {
    //'sums' hastable holds all possible sums a[k] + a[l]
    //where k and l are both less than i

    for (int j = i + 1; j < n; ++j) {
        int current = a[i] + a[j];
        int rest = X - current;
        //Now we need to find if there're different numbers k and l
        //such that a[k] + a[l] == rest and k < i and l < i
        //but we have 'sums' hashtable prepared for that
        if (sums[rest] != null) {
            //found it
        }
    }

    //now let's put in 'sums' hashtable all possible sums
    //a[i] + a[k] where k < i
    for (int k = 0; k < i; ++k) {
        sums[a[i] + a[k]] = pair(i, k);
    }
}

Disons, X = a[1] + a[3] + a[7] + a[10]. Cette somme sera trouvé quand i = 7, j = 10 et rest = a[1] + a[3] (indices 1 et 3 seront trouvés à partir de hachage)

OriginalL'auteur Nikita Rybak

Abuser du fait qu'aucune mémoire ne contraignent est spécifié. Et à l'aide de l'habitude de diviser et conquérir approche.

Nombre de toutes les permutations pour 4 nombre de sous-ensembles est C(n,4) et est O(n^4). Nombre de toutes les permutations de 2 nombres est C(n,2) et O(n^2). O(n^2) semble être OK pour la tâche.

1. D'entrée: un tableau A avec n éléments, X.
2. Générer toutes les permutations pour 2 nombre de sous-ensembles (O(n^2)) et de mettre leurs sommes dans un tableau B avec n^2 éléments (aussi se souvenir de la sous-ensembles). Nous allons désigner comme S[B[i]] le sous-ensemble (composé de deux chiffres) dont la somme est B[i].
3. Trier les B, O(n^2*log(n^2)).

4. À pied à travers le tableau B (O(n^2)) i = [0,n^2) et de recherche rapide O(log(n^2)) = O(log(n)) pour la valeur (X - B[i]). Il existe peut-être plusieurs d'entre eux (mais pas plus de n^2).

   4.1. Marcher à travers tous les éléments dont la valeur de (X - B[i]), à l'aide de l'indice de k.

   4.2. Ignorer les éléments B[k] où S[B[k]] croise S[B[i]]. Intersection de deux ensembles, avec deux numéros peut être calculé en temps O(1).

   4.3 Si k est l'indice d'un élément où B[i] + B[k] == X et S[B[k]] ne coupe pas avec S[B[i]], alors la somme des ensembles S[B[k]] et S[B[i]] sont les quatre cherché numéros.

Performance est:
O( n^2 + n^2*log(n^2) + n^2*log(n^2) ) = O( n^2 * log(n^2) ) = O( n^2 * log(n) )

Sur l'étape quatre, lorsque nous itérer sur les multiples éléments correspondants de B à l'aide de boucles imbriquées. Pourtant, le nombre total d'itérations de deux boucles imbriquées est limitée par la |B| qui est O(n^2). La recherche rapide n'est pas l'habitude de variation, mais celui qui trouve l'élément correspondant à l'indice le plus bas. (Alternativement, on peut utiliser l'habituel bsearch et depuis nous pourrions avoir atterri dans le milieu, utiliser deux boucles adjacentes, en vérifiant les éléments dans les deux directions.)

OriginalL'auteur Dummy00001

1) Créer un tableau de tous les possibles paire sommes [O(N^2)]

2) Trier ce tableau dans l'ordre croissant [O(N^2 * Log N)]

3) Maintenant, ce problème se réduit à trouver 2 nombres dans un tableau trié que la somme d'un nombre donné X, dans le temps linéaire. Utiliser 2 pointeurs: un FAIBLE pointeur à partir de la valeur la plus basse, et un HAUT pointeur à partir de la valeur la plus élevée. Si la somme est trop faible, FAIBLE avance. Si la somme est trop élevée, l'avance de HAUT (vers l'arrière). Ils finiront par trouver la paire ou de la croix les uns des autres (ce qui peut être facilement prouvé). Ce processus prend du temps linéaire en la taille du tableau, c'est à dire O(N ^ 2)

Cela donne un temps total de O(N^2 * log N).

NOTE : Cette méthode peut être généralisée pour résoudre le cas de M nombres en O(M * N^(M/2) * log N) fois.

-- EDIT --

En fait, ma réponse est très similaire à Dummy00001 de réponse, à l'exception de la finale de la recherche, où j'utilise une méthode plus rapide (bien que la complexité globale est la même chose...)

OriginalL'auteur Eyal Schneider

Je ne vais pas répondre à votre question complètement, car je pense que c'est les devoirs et pense aussi que c'est facile à faire. Mais je pense que je sais pourquoi vous avez de la difficulté à répondre, alors je vais vous aider un peu.

Tout d'abord, vous devez regarder dans la récursivité. Cela signifie que l'appel d'une fonction à partir de l'intérieur de lui-même.

Seconde, vous devriez utiliser une fonction d'assistance, qui est appelée par la fonction que vous voulez écrire. Cette fonction doit prendre comme arguments:
- un tableau de nombres
- la longueur du tableau
- la valeur que vous voulez trouver les membres de cette somme jusqu'à
- le nombre de membres de la matrice que vous voulez pour résumer

Cette fonction sera appelée par votre autre fonction et passé un 4 pour le dernier argument. Il va alors appeler lui-même en ajustant les arguments qu'il essaie de trouver des résultats en partie, d'essai et d'erreur.

edit 2

Sur la poursuite de la réflexion, j'ai réalisé que ce n'est pas O(n^2), comme je l'ai affirmé plus tôt (je mentalement omis de le moyen étapes). Elle est limitée par le n^4, mais peut avoir une limite inférieure à celle due à l'amplement l'occasion de couper court dans de nombreux cas. Je ne crois pas que ce court coupe améliore au point de n^2.

OriginalL'auteur nategoose

J'ai écrit un O(N^^2) temps d'exécution d'une fonction qui n'utilise pas de tables de hachage, mais les poignées de nombres négatifs et les nombres en double apparemment OK. J'gérer les nombres négatifs dans un tableau d'entiers par l'ajout d'un grand postive(par exemple 100) pour tous les entiers dans le tableau. Ensuite, je ajuster la cible par target += (4 * 100). Puis, quand je trouve un résultat, je soustrais les 100 de les entiers dans le résultat. Voici mon code et des cas de test: s'il vous Plaît laissez-moi savoir si cela o(N^^2) le temps de la complexité.

struct maryclaranicholascameron{
int sum;
int component1;
int component2;
};
void Another2PrintSum(int arr[], int arraysize, int target){
int i(arraysize -1);
int j(arraysize -2);
int temp(target);
int temp2(0);
int m(0);
int n(0);
int sum(0);
int original_target(target);
for (int ctr = 0; ctr < arraysize; ctr++){
sum += arr[ctr];
}
for (int ctrn = 0; ctrn < arraysize; ctrn++){
arr[ctrn] += 100;
}
maryclaranicholascameron* temparray = new maryclaranicholascameron[sum + (arraysize *100)];
memset(temparray, 0, sizeof(maryclaranicholascameron) * (sum + 400));
for (m = 0; m < arraysize; m++){
for (n = m + 1; n < arraysize; n++){
temparray[arr[m] + arr[n]].sum = arr[m]+ arr[n];
temparray[arr[m] + arr[n]].component1 = m;
temparray[arr[m] + arr[n]].component2 = n;
}
}
target += (4 * 100);
original_target = target;
bool found(false);
while (i >= 0 && i < arraysize && found == false){
target -= (arr[i]);
while(j >= 0 && j < arraysize && found == false){
temp2 = target;
target -= (arr[j]);
if (i != j && temparray[target].sum == target && 
temparray[target].sum != 0 &&
temparray[target].component1 != i &&
temparray[target].component2 != i &&
temparray[target].component1 != j &&
temparray[target].component2 != j){
printf("found the 4 integers i = %d j = %d m = %d n = %d component1 = %d component = %d i %d j %d\n",
arr[i] - 100,
arr[j] - 100,
arr[temparray[target].component1] - 100,
arr[temparray[target].component2] - 100,
temparray[target].component1,
temparray[target].component2,
i,
j);
found = true;
break;
}
j -= 1;
target = temp2;
}
i -= 1;
j = i;
target = original_target;
}
if (found == false){
printf("cannot found the 4 integers\n");
}
delete [] temparray;
}
//test cases
int maryclaranicholas[] = { -14,-14,-14,-14,-12 ,-12, -12 ,-12 ,-11, -9,-8,-7,40};
Another2PrintSum(maryclaranicholas, 13,-2};
int testarray[] = {1,3,4,5,7,10};
Another2PrintSum(testarray, 6, 20);

OriginalL'auteur Frank

Ce problème peut être considéré comme une variation de pascals identité,

voici le code complet :

s'il vous plaît excuser, comme le code est en java :

public class Combination {
static int count=0;
public static void main(String[] args) {
int a[] =  {10, 20, 30, 40, 1, 2,4,11,60,15,5,6};
int setValue = 4;
getCombination(a, setValue);
}
private static void getCombination(int[] a, int setValue) {
//TODO Auto-generated method stub
int size = a.length;
int data[] = new int[setValue];
createCombination(a, data, setValue, 0, 0, size);
System.out.println(" total combinations : "+count);
}
private static void createCombination(int[] a, int[] data, int setValue,
int i, int index, int size) {
//TODO Auto-generated method stub
if (index == setValue) {
if(data[0]+data[1]+data[3]+data[2]==91)
{   count ++;
for (int j = 0; j < setValue; j++)
System.out.print(data[j] + " ");
System.out.println();
}return;
}
//System.out.println(". "+i);
if (i >= size)
return;
//to take care of repetation
if (i < size - 2) {
while (a[i] == a[i + 1])
i++;
}
data[index] = a[i];
//System.out.println(data[index]+" "+index+"  .....");
createCombination(a, data, setValue, i + 1, index + 1, size);
createCombination(a, data, setValue, i + 1, index, size);
}

}

D'entrée d'échantillon :

int a[] =  {10, 20, 30, 40, 1, 2,4,11,60,15,5,6};

De sortie : :

10 20 1 60 
10 30 40 11 
10 60 15 6 
20 30 40 1 
20 60 5 6 
30 40 15 6 
11 60 15 5 
total combinations : 7

OriginalL'auteur sourav palmal