Die Anzahl der verschiedenen Paare von Ganzzahlen, die zu einer Ganzzahl summieren

Question

Ich versuche, die Anzahl der Paare in einem Array so zu zählen, dass jedes Paar die Summe einer ganzen Zahl gibt!

habe ich den folgenden Code:

public static int SumPairs(Integer []input, int k){ 
    Map<Integer, Integer> pairs = new HashMap<Integer, Integer>(); 
    int tmp=0; 
    //System.out.println(pairs.toString()); 
    for(int i=0;i<input.length;i++){ 
    if(pairs.containsKey(input[i])){ 
      System.out.println(pairs.containsKey(input[i])); 
      System.out.println(input[i] +", "+ pairs.get(input[i])); 
      input[i]=0; 
      tmp++;  

     } 

     else 
      pairs.put(k-input[i], input[i]); 
    }return tmp; 
} 

das Problem ist; zum Beispiel, wenn mein Array 1 2 2 2 3 4 4 4 und sum = 5 es wie folgt

(4,1) 
(4,1) 
(4,1) 
(3,2) 

berechnen möchte ich die Methode von der Verwendung einer Anzahl mehr als einmal verhindern !! so dass der Ausgang

(4,1) 
(3,2) 

Answer 1

Ich benutze einen Kartenwerte und ihre Frequenzen zu speichern:

public static int SumPairs(Integer[] input, int k){ 
    Map<Integer, Integer> frequencies = new HashMap<>(); 
    int pairsCount = 0;  

    for(int i=0; i<input.length; i++){ 
     int value = input[i]; 
     int complement = k - input[i]; 

     if(frequencies.containsKey(complement)){     
      int freq = frequencies.get(complement) - 1; 
      pairsCount++; 
      //System.out.println(value + ", " + complement);  
      if(freq == 0){ 
       frequencies.remove(complement); 
      }else{ 
       frequencies.put(complement, freq); 
      } 
     }else{ 
      if(frequencies.containsKey(value)){   
       frequencies.put(value, frequencies.get(value) + 1);    
      }else{ 
       frequencies.put(value, 1); 
      } 
     } 
    } 
    return pairsCount; 
} 

Answer 2

public static int sumPairs(Integer[] input, int sum){ 
    List<Integer> complementaries = new ArrayList<>(input.length); 
    int pairs = 0; 
    for(Integer number : input){ 
     if(complementaries.contains(number)){ 
      complementaries.remove(number); 
      pairs++; 
     } 
     else{ 
      complementaries.add(sum-number); 
     } 
    } 
    return pairs; 
} 

Jetzt sollte es funktioniert perfekt sein wird.

Das Komplementär-Array wird nur dazu verwendet, die Anzahl der für die Summe benötigten Zahlen zu verfolgen. Wenn es die Zahl enthält, bedeutet dies, dass wir über seine Ergänzung vor iteriert haben, also können wir einfach ein Paar hinzufügen und die Zahl aus der Liste der Komplementärzeichen entfernen. Oherwise fügen wir der Liste die Komplementärzahl der aktuellen Zahl hinzu, ohne den Paarknoten zu erhöhen.