Finden Sie die Anzahl der verschiedenen Paare von Zahlen, deren Summe gleich 'K' ist - PHP

Question

Gegeben ein Array, ich möchte die Anzahl der verschiedenen Paare von Elementen anzeigen, deren Summe gleich K - Ich habe Code geschrieben wie unten, aber ich bin nicht in der Lage für einen guten Zweck zu setzen array_diff: \

<?PHP 
function numberOfPairs($a, $k) { 
    $cnt = 0; 
    for($i=0; $i<count($a); $i++){ 
     for($j=$i; $j<count($a); $j++){ 
      if($a[$i]+$a[$j] == $k){ 
       $arrRes[$i][0] = $a[$i]; 
       $arrRes[$i][1] = $a[$j]; 
       $cnt++; 
      } 
     } 
    } 
    sort($arrRes); 
    //print $cnt; 
    $d = $cnt; 
    for($i=0; $i<count($arrRes); $i++){ 
     for($j=0; $j<count($arrRes); $j++){ 
      $diff = array_diff($arrRes[$i], $arrRes[$j]); 
      if($diff == null) 
       $d += 1; 
     } 
    } 
    print $d; 
} 

$a = [6,6,3,9,3,5,1]; 
$k = 12; 
numberOfPairs($a, $k); 
?> 

Hier werden die Ausgangsfelder mit Summe gleich 12 sind, das heißt, das Ergebnis von $ arrRes ist -

[0] => Array ([0] => 3 [1] => 9) 
[1] => Array ([0] => 6 [1] => 6) 
[2] => Array ([0] => 6 [1] => 6) 
[3] => Array ([0] => 9 [1] => 3) 

Die Zählung ist 4, aber die Zählung sollte 2 sein, da (6,6) und (3,9) die einzigen unterschiedlichen Paare sind.

Answer 1

Sie können ein flaches Array mit verwendeten Nummern erstellen und überprüfen, damit Sie sie nicht erneut mit in_array verwenden.

function numberOfPairs($a, $k) { 
    $cnt = 0; 
    $used=[]; 
    for($i=0; $i<count($a); $i++){ 
     for($j=$i; $j<count($a); $j++){ 
      if($a[$i]+$a[$j] == $k && !in_array($a[$i], $used) && !in_array($a[$i],$used)){ 
       $arrRes[$i][0] = $a[$i]; 
       $arrRes[$i][1] = $a[$j]; 
       $used[] = $a[$i]; 
       $used[] = $a[$j]; 
       $used = array_unique($used); 
       $cnt++; 
      } 
     } 
    } 
    sort($arrRes); 
    //print $cnt; 
    // Not sure what the code below does, but I just left it the way it was. 
    $d = $cnt; 
    for($i=0; $i<count($arrRes); $i++){ 
     for($j=0; $j<count($arrRes); $j++){ 
      $diff = array_diff($arrRes[$i], $arrRes[$j]); 
      if($diff == null) 
       $d += 1; 
     } 
    } 
    print $d; 
} 

$a = [6,6,3,9,3,5,1]; 
$k = 12; 
numberOfPairs($a, $k); 

Probieren Sie es hier https://3v4l.org/lDe5V

Answer 2

Sie Ihre Lösung vereinfachen kann, indem Tatsache mit, dass Arrays in php Hashmaps sind:

function numberOfPairs($a, $k) { 
    $used=[]; 
    for ($i=0; $i<count($a); $i++) 
     for ($j=$i+1; $j<count($a); $j++) { 
      $v1 = min($a[$i], $a[$j]); 
      $v2 = max($a[$i], $a[$j]); 
      if ($k == $v1+$v2) 
       $used[$v1.'_'.$v2] = true; 
     } 
    return count($used); 
} 

$a = [6,6,3,9,3,5,1]; 
$k = 12; 
echo numberOfPairs($a, $k); 

Answer 3

Sortieren Array und bewegen Indizes von beiden Enden, bis sie nicht sind Überlappung, die O (n log n) anstelle von O (n^2) in akzeptierter Antwort erhält

function numberOfPairs($a, $k) { 
    sort($a); 
    $i = 0; 
    $j = count($a)-1; 
    // save last inseted array to avoid duplicates 
    $last = []; 
    while($i < $j) { 
    $s = $a[$i] + $a[$j]; 
    if($s == $k) { 
     $t = [$a[$i++], $a[$j--]]; 
     // Check for duplicate 
     if ($t != $last) { 
     $d[] = [$a[$i++], $a[$j--]]; 
     $last = $t; 
     } 
    } 
    elseif($s > $k) $j--; 
    else $i++; 
    } 
    return $d; 
} 

demo

Answer 4

Dies ist meine Methode, um verschiedene Paare von Addenden zu finden, die ein Array und eine Zielsumme haben.

• array_count_values() wird die Eingangsfeldgröße durch Kondensieren doppelte Addenden reduzieren und sie als Schlüssel (und deren Anzahl von Vorkommen als Werte) speichert.
• ksort() wird aufgerufen, um sicherzustellen, dass die Summanden in aufsteigender Reihenfolge verarbeitet werden. Dies ist wichtig, um die Verarbeitung von Summanden zu vermeiden, die über den Mittelpunkt des Nummernsatzes hinausgehen.
• jede Iteration, Speicher Summanden, die "kleiner als oder gleich" die Hälfte von k UND haben einen übereinstimmenden Summanden.
• Wenn der mit 2 multiplizierte Summand "größer als oder gleich" k ist, wird die Iteration nicht fortgesetzt.

Code: (Demo)

function numberOfPairs($a,$k){ 
    $a=array_count_values($a); // enable use of the very fast isset() function and avoid iterating duplicates 
    ksort($a); // order so that only the lower values need to be iterated 
    foreach($a as $num=>$occur){ 
     if(($double=$num*2)>=$k){ // we are at or past the middle 
      if($double==$k && $occur>1) $result[]=[$num,$k-$num]; // addends are equal and 2 exist, store before break 
      break; 
     }elseif(isset($a[$k-$num])){ // matching addend found, store & continue 
      $result[]=[$num,$k-$num]; 
     } 
    } 
    var_export($result); 
} 

$a = [6,6,3,9,3,5,1]; 
$k = 12; 
numberOfPairs($a,$k); 

Ausgang:

array (
    0 => 
    array (
    0 => 3, 
    1 => 9, 
), 
    1 => 
    array (
    0 => 6, 
    1 => 6, 
), 
) 

array_count_values() ist wahrscheinlich die teuerste Funktionsaufruf im Snippet, aber es setzt alle nachfolgenden Prozesse bis schnell, prägnant, direkt und logisch (und ich denke, lesbar).