utiliser radix sort en place et la première solution D'OP avec 2 itérateurs, venant l'un vers l'autre.

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

détails pour la solution des 2 itérateurs:

le premier itérateur pointe d'abord vers le premier élément du tableau trié et avance. 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és par les itérateurs est inférieure à la valeur requise, avancer le premier itérateur. Si elle est supérieure à la valeur requise, avancez second itérateur. Si elle est égale à la valeur requise, le succès.

un seul le pass est nécessaire, donc la complexité temporelle est O (n). L'espace de la complexité est O(1). Si le tri radix est utilisé, les complexités de l'algorithme entier sont les mêmes.

si vous êtes intéressé par des problèmes apparentés (avec la somme de plus de 2 nombres), voir "Sum-subset with a fixed subset size" et "trouver trois éléments dans un tableau dont la somme est la plus proche d'un nombre donné" .

il s'agit d'une question d'entrevue classique de Microsoft research Asia.

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

[1]solution de force brute

Cet algorithme est très simple. La complexité temporelle est O(N^2)

[2]Recherche binaire

En utilisant la recherche bianry pour trouver la somme-arr[i] avec chaque arr[i], la complexité du temps peut être réduite à O (N * logN)

[3]Utilisant Le Hash

En se basant sur l'algorithme [2] et en utilisant le hachage, la complexité temporelle peut être réduite à O(N), mais cette solution ajoutera l'espace O(N) du 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 cette question est-elle résolue? Aucun. Si le nombre est N. ce problème deviendra très complexe.

la question alors:

Comment puis-je trouver tous les cas de combinaison avec un nombre donné?

il s'agit d'un NP classique-problème complet qui s'appelle sous-ensemble-somme.

Pour comprendre NP/NPC / NP-dur, vous feriez mieux de lire des livres professionnels.

, les 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

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.

si vous supposez que la valeur M à laquelle les paires sont supposées additionner est constante et que les entrées dans le tableau sont positives, alors vous pouvez le faire en un passage ( O(n) time) en utilisant M/2 pointeurs ( O(1) space) comme suit. Les pointeurs sont étiquetés P1,P2,...,Pk où k=floor(M/2) . Alors faites quelque chose comme ça

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 (par exemple deux 6's) en stockant les indices sous forme de chiffres dans la 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.

    public void printPairsOfNumbers(int[] a, int sum){
    //O(n2)
    for (int i = 0; i < a.length; i++) {
        for (int j = i+1; j < a.length; j++) {
            if(sum - a[i] == a[j]){
                //match..
                System.out.println(a[i]+","+a[j]);
            }
        }
    }

    //O(n) time and O(n) space
    Set<Integer> cache = new HashSet<Integer>();
    cache.add(a[0]);
    for (int i = 1; i < a.length; i++) {
        if(cache.contains(sum - a[i])){
            //match//
            System.out.println(a[i]+","+(sum-a[i]));
        }else{
            cache.add(a[i]);
        }
    }

}

est-ce la solution la plus évidente de ne pas travailler (une itération sur chaque consécutives paire) ou sont les deux nombres dans n'importe quel ordre?

dans ce cas, vous pouvez trier la liste des nombres et utiliser l'échantillonnage aléatoire pour diviser la liste triée jusqu'à ce que vous ayez une sous-liste qui est assez petite pour être itérée plus.

public static ArrayList<Integer> find(int[] A , int target){
    HashSet<Integer> set = new HashSet<Integer>();
    ArrayList<Integer> list = new ArrayList<Integer>();
    int diffrence = 0;
    for(Integer i : A){
        set.add(i);
    }
    for(int i = 0; i <A.length; i++){
        diffrence = target- A[i];
    if(set.contains(diffrence)&&A[i]!=diffrence){
        list.add(A[i]);
        list.add(diffrence);
        return list;
    }
     }
    return null;
}

`package algorithmsDesignAnalysis;

 public class USELESStemp {
 public static void main(String[] args){
    int A[] = {6, 8, 7, 5, 3, 11, 10}; 

    int sum = 12;
    int[] B = new int[A.length];
    int Max =A.length; 

    for(int i=0; i<A.length; i++){
        B[i] = sum - A[i];
        if(B[i] > Max)
            Max = B[i];
        if(A[i] > Max)
            Max = A[i];

        System.out.print(" " + B[i] + "");

    } // O(n) here; 

    System.out.println("\n Max = " + Max);

    int[] Array = new int[Max+1];
    for(int i=0; i<B.length; i++){
        Array[B[i]] = B[i];
    } // O(n) here;

    for(int i=0; i<A.length; i++){  
    if (Array[A[i]] >= 0)
        System.out.println("We got one: " + A[i] +" and " + (sum-A[i]));
    } // O(n) here;

} // end main();

/******
Running time: 3*O(n)
*******/
}

ci-dessous le code prend le tableau et le nombre N comme la somme cible. D'abord, le tableau est trié, puis un nouveau tableau contenant les les éléments restants sont pris et ensuite scannés pas par recherche binaire mais le balayage simple du reste et du tableau simultanément.

public static int solution(int[] a, int N) {

    quickSort(a, 0, a.length-1);    // nlog(n)

    int[] remainders = new int[a.length];

    for (int i=0; i<a.length; i++) {
        remainders[a.length-1-i] = N - a[i];     // n
    }

    int previous = 0;

    for (int j=0; j<a.length; j++) {            // ~~ n

        int k = previous;

        while(k < remainders.length && remainders[k] < a[j]) {
            k++;
        }

        if(k < remainders.length && remainders[k] == a[j]) {
            return 1;
        }

        previous = k;
    }

    return 0;
}

ne devrait-il pas itérer des deux côtés pour résoudre le problème?

trier le tableau. Et de commencer la comparaison des deux extrémités.

if((arr[start] + arr[end]) < sum) start++;
if((arr[start] + arr[end]) > sum) end--;
if((arr[start] + arr[end]) = sum) {print arr[start] "," arr[end] ; start++}
if(start > end)  break;

Complexité Temporelle O(nlogn)

si c'est un trié tableau et nous n'avons besoin que de paires de nombres et pas toutes les paires nous pouvons le faire comme ceci:

public void sums(int a[] , int x){ // A = 1,2,3,9,11,20 x=11
    int i=0 , j=a.length-1;
    while(i < j){
      if(a[i] + a[j] == x) system.out.println("the numbers : "a[x] + " " + a[y]);
      else if(a[i] + a[j] < x) i++;
      else j--;
    }
}

1 2 3 9 11 20 || i=0 , j = 5 somme = 21 x=11

1 2 3 9 11 20 || i=0 , j = 4 somme = 13 x=11

1 2 3 9 11 20 || i=0 , j = 4 somme=11 x=11

Fin

le code suivant renvoie true si deux entiers dans un tableau correspondent à un entier comparé.

 function compareArraySums(array, compare){

        var candidates = [];

        function compareAdditions(element, index, array){
            if(element <= y){
                candidates.push(element);
            }
        }

        array.forEach(compareAdditions);

        for(var i = 0; i < candidates.length; i++){
            for(var j = 0; j < candidates.length; j++){
                if (i + j === y){
                    return true;
                }
            }
        }
    }

Python 2.7 Mise En Œuvre:

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

https://github.com/clockzhong/findSumPairNumber

#! /usr/bin/env python
import sys
import os
import re


#get the number list
numberListStr=raw_input("Please input your number list (seperated by spaces)...\n")
numberList=[int(i) for i in numberListStr.split()]
print 'you have input the following number list:'
print numberList

#get the sum target value
sumTargetStr=raw_input("Please input your target number:\n")
sumTarget=int(sumTargetStr)
print 'your target is: '
print sumTarget


def generatePairsWith2IndexLists(list1, list2):
    result=[]
    for item1 in list1:
        for item2 in list2:
            #result.append([item1, item2])
            result.append([item1+1, item2+1])
    #print result
    return result

def generatePairsWithOneIndexLists(list1):
    result=[]
    index = 0
    while index< (len(list1)-1):
        index2=index+1
        while index2 < len(list1):
            #result.append([list1[index],list1[index2]])
            result.append([list1[index]+1,list1[index2]+1])
            index2+=1
        index+=1
    return result


def getPairs(numList, target):
    pairList=[]
    candidateSlots=[] ##we have (target-1) slots 

    #init the candidateSlots list
    index=0
    while index < target+1:
        candidateSlots.append(None)
        index+=1

    #generate the candidateSlots, contribute O(n) complexity
    index=0
    while index<len(numList):
        if numList[index]<=target and numList[index]>=0:
            #print 'index:',index
            #print 'numList[index]:',numList[index]     
            #print 'len(candidateSlots):',len(candidateSlots)
            if candidateSlots[numList[index]]==None:
                candidateSlots[numList[index]]=[index]
            else:
                candidateSlots[numList[index]].append(index)
        index+=1

    #print candidateSlots

    #generate the pairs list based on the candidateSlots[] we just created
    #contribute O(target) complexity
    index=0
    while index<=(target/2):
        if candidateSlots[index]!=None and candidateSlots[target-index]!=None:
            if index!=(target-index):
                newPairList=generatePairsWith2IndexLists(candidateSlots[index], candidateSlots[target-index])
            else:
                newPairList=generatePairsWithOneIndexLists(candidateSlots[index])
            pairList+=newPairList
        index+=1

    return pairList

print getPairs(numberList, sumTarget)

j'ai implémenté avec succès une solution avec Python sous O(n+m) time and space cost. Le" m " est la valeur cible à laquelle la somme de ces deux nombres doit être égale. Je crois que c'est le coût le plus bas possible. Erict2k utilise des outils itératifs.les combinaisons, il en coûtera également similaire ou plus de temps et d'espace coût de comparer mon algorithme.

si les nombres ne sont pas très grands, vous pouvez utiliser la Transformée de fourier rapide pour multiplier deux polynômes et puis dans O(1) vérifier si le coefficient avant x^(somme nécessaire) somme est plus que zéro. O(n log n) total de la!

// Java mise en œuvre à l'aide de Hachage importer java.io.*;

classe PairSum { private static final int MAX = 100000; / / Max size of Hashmap

static void printpairs(int arr[],int sum)
{
    // Declares and initializes the whole array as false
    boolean[] binmap = new boolean[MAX];

    for (int i=0; i<arr.length; ++i)
    {
        int temp = sum-arr[i];

        // checking for condition
        if (temp>=0 && binmap[temp])
        {
            System.out.println("Pair with given sum " +
                                sum + " is (" + arr[i] +
                                ", "+temp+")");
        }
        binmap[arr[i]] = true;
    }
}

// Main to test the above function
public static void main (String[] args)
{
    int A[] = {1, 4, 45, 6, 10, 8};
    int n = 16;
    printpairs(A,  n);
}

}

créer un dictionnaire avec la clé de paires (nombre de la liste) et la valeur est le nombre qui est nécessaire pour obtenir une valeur désirée. Ensuite, vérifiez la présence des paires de nombres dans la liste.

def check_sum_in_list(p_list, p_check_sum):
    l_dict = {i: (p_check_sum - i) for i in p_list}
    for key, value in l_dict.items():
        if key in p_list and value in p_list:
            return True
    return False


if __name__ == '__main__':
    l1 = [1, 3, 7, 12, 72, 2, 8]
    l2 = [1, 2, 2, 4, 7, 4, 13, 32]

    print(check_sum_in_list(l1, 10))
    print(check_sum_in_list(l2, 99))

Output:
True
Flase

version 2

import random


def check_sum_in_list(p_list, p_searched_sum):
    print(list(p_list))
    l_dict = {i: p_searched_sum - i for i in set(p_list)}
    for key, value in l_dict.items():
        if key in p_list and value in p_list:
            if p_list.index(key) != p_list.index(value):
                print(key, value)
                return True
    return False


if __name__ == '__main__':
    l1 = []
    for i in range(1, 2000000):
        l1.append(random.randrange(1, 1000))

    j = 0
    i = 9
    while i < len(l1):
        if check_sum_in_list(l1[j:i], 100):
            print('Found')
            break
        else:
            print('Continue searching')
            j = i
            i = i + 10

Output:
...
[154, 596, 758, 924, 797, 379, 731, 278, 992, 167]
Continue searching
[808, 730, 216, 15, 261, 149, 65, 386, 670, 770]
Continue searching
[961, 632, 39, 888, 61, 18, 166, 167, 474, 108]
39 61
Finded
[Finished in 3.9s]

    public static void Main(string[] args)
    {
        int[] myArray =  {1,2,3,4,5,6,1,4,2,2,7 };
        int Sum = 9;

            for (int j = 1; j < myArray.Length; j++)
            {                    
                if (myArray[j-1]+myArray[j]==Sum)
                {
                    Console.WriteLine("{0}, {1}",myArray[j-1],myArray[j]);
                }
            }            
        Console.ReadLine();
    }