Ich bin ziemlich neu in der Codierung und habe mich für die tägliche Mailingliste für Codierungsprobleme angemeldet und diese Frage erhalten:

Geben Sie bei einer gegebenen Liste von Zahlen und einer Zahl k zurück, ob sich zwei beliebige Zahlen aus der Liste zu k addieren.

Meine Lösung (nach einigem Stackoverflow-Graben) sieht folgendermaßen aus.

function problemOne_Solve()
{
    const k = 17;
    const values = [11, 15, 3, 8, 2];
    for (i=0; i < values.length; i++) {
        if ( values.find( (sum) => { return k-values[i] === sum} ) ) return true;
    }
    return false;
}

Ich frage mich, warum es funktioniert. Für mich sieht es so aus, als ob der Teil mit der Fettpfeilfunktion die Klammern in der bedingten Logik der if-Anweisungen schließt. Und nach der if-Anweisung, die ich für erforderlich hielt, gibt es keine solchen Klammern.

Ich habe mich auch gefragt, wie ich das Paar oder die Paare ausgeben soll, die sich zu "k" summieren, um weiter auf der Lösung aufzubauen. Ich möchte zum Beispiel die Paare auf der Seite anzeigen können.

6
Maximilian Lunde Skjønhaug 24 Feb. 2020 im 11:24

3 Antworten

Beste Antwort

.find nimmt einen Rückruf entgegen, der für jedes Element im Array aufgerufen wird (oder bis eine Übereinstimmung gefunden wird). Das erste Argument für den Rückruf ist das Element, über das iteriert wird. Wenn eine Übereinstimmung gefunden wird (wenn der Rückgabewert aus dem Rückruf für ein Element wahr war), gibt .find das Element zurück, das zu einem wahrheitsgemäßen Rückgabewert geführt hat.

Bei der ersten i = 0 Iteration und values[i] ist 11 prüft (sum) => { return k-values[i] === sum} zuerst, ob 17 - 11 === 11 und dann 17 - 11 === 15 und dann ob 17 - 11 = 3 usw.

Diese Bedingung ist im Allgemeinen erfüllt, wenn sich zwei Zahlen im Array zu k addieren, der Algorithmus jedoch fehlerhaft ist. Beispielsweise überprüft ein Array aus [1] die 1 bei der ersten Iteration gegen sich selbst und addiert sich zu 2:

function problemOne_Solve() {
    const k = 2;
    const values = [1];
    for (i=0; i < values.length; i++) {
        if ( values.find( (sum) => { return k-values[i] === sum} ) ) return true;
    }
    return false;
}

console.log(problemOne_Solve());

Das ist falsch. Ein weiteres Problem ist, dass .find den gefundenen Wert zurückgibt. Wenn das Array jedoch ein Array von Zahlen ist, kann der gefundene Wert 0 sein und 0 ist falsch. Das folgende Beispiel sollte also true zurückgeben, da zwei Elemente zu 0 (0 und 0) summieren, aber false zurückgeben:

function problemOne_Solve() {
    const k = 0;
    const values = [0, 0];
    for (i=0; i < values.length; i++) {
        if ( values.find( (sum) => { return k-values[i] === sum} ) ) return true;
    }
    return false;
}

console.log(problemOne_Solve());

Um es richtig zu machen und die Rechenkomplexität von O(n ^ 2) auf O(n) zu verringern, durchlaufen Sie das Array einmal . Erstellen Sie ein Objekt, dessen Schlüssel die Zahlen sind, über die iteriert wird, und überprüfen Sie bei jeder Iteration, ob auf dem Objekt ein Schlüssel von target - currNum vorhanden ist (wobei target die Zielsumme ist und {{X4}) } ist die aktuelle Nummer aus dem Array):

function problemOne_Solve() {
  const target = 17;
  const values = [11, 15, 3, 8, 2];
  const obj = {};
  for (const currNum of values) {
    if (obj.hasOwnProperty(target - currNum)) {
      return true;
    }
    obj[currNum] = true;
  }
  return false;
}
console.log(problemOne_Solve());

Ich habe mich auch gefragt, wie ich das Paar oder die Paare ausgeben soll, die sich zu "k" summieren, um weiter auf der Lösung aufzubauen. Ich möchte zum Beispiel die Paare auf der Seite anzeigen können.

Anstatt sofort zurückzukehren, wenn eine Übereinstimmung gefunden wird, drücken Sie auf ein Array und geben Sie dieses Array am Ende der Funktion zurück. Anstatt die Objektwerte auf true (oder false) zu setzen, setzen Sie sie auf die Anzahl der Vorkommen, bei denen die Anzahl bisher gefunden wurde (und verringern Sie die übereinstimmende Nummer, wenn eine Übereinstimmung gefunden wird):

function problemOne_Solve() {
  const target = 17;
  const values = [11, 15, 3, 8, 2, 17, 0, 0, 17];
  const obj = {};
  const matches = [];
  for (const currNum of values) {
    const otherNum = target - currNum;
    if (obj[otherNum]) {
      obj[otherNum]--;
      matches.push([currNum, otherNum]);
    }
    obj[currNum] = (obj[currNum] || 0) + 1;
  }
  return matches;
}
console.log(problemOne_Solve());

Und nach der if-Anweisung, die ich für erforderlich hielt, gibt es keine solchen Klammern.

Klammern sind nicht erforderlich, wenn nach einem if (oder else if oder else) eine einzelne Anweisung steht, z.

if (true) console.log('true');
else console.log('this will not log');
3
CertainPerformance 24 Feb. 2020 im 08:41

Und nach der if-Anweisung, die ich für erforderlich hielt, gibt es keine solchen Klammern.

Wenn nach if else nur eine Anweisung steht, werden die Klammern optional. Idealerweise sollten Sie nicht schreiben, dass der if -Block eine Zeile ist, um Ihren Code sauber zu machen

Als Anfänger würde ich Ihnen empfehlen, einfache for Schleifen anstelle dieser ausgefallenen Methoden wie find zu verwenden.

Sie können dies in folgenden Schritten tun:

  • Es ist klar, dass Sie die Summe jedes Elements mit jedem anderen Element des Arrays benötigen. Sie benötigen also eine verschachtelte Schleifenstruktur
  • Die äußere Schleife oder Hauptschleife beginnt bei 0 und endet am Ende des Arrays.
  • Sie müssen eine innere Schleife oder eine verschachtelte Schleife erstellen, die vom Index nach dem aktuellen Index beginnt.
  • In jeder Iteration einer verschachtelten Schleife müssen Sie überprüfen, ob die Summe zweier Elemente gleich requiredSum ist oder nicht.
function pairWithSum(givenArray, requiredSum){
  for(let i = 0; i < givenArray.length; i++){
    for(let j = i + 1; j < givenArray.length; j++){
      let sum = givenArray[i] + givenArray[j];
      if(sum === requiredSum){
        return [givenArray[i], givenArray[j]];
      }
    }
  }
  return false
}

console.log(pairWithSum([1, 4, 5, 8], 12));
console.log(pairWithSum([1, 4, 5, 8], 15));
0
Maheer Ali 24 Feb. 2020 im 08:36

Ich frage mich, warum es funktioniert

Dies liegt daran, dass if erwartet, dass ein Ausdruck / eine Anweisung validiert wird.

values.find( (sum) => { return k-values[i] === sum} )

Dies ist eine Anweisung, die zuvor ausgewertet und ihre Ausgabe zur Bedingung an if übergeben wird.

Jetzt hat Array.find einen Rückgabetyp: T|<null> wobei T ein beliebiges Wertearray ist. Wenn also values[i] in der zweiten Iteration auf 15 verweist, wird 2 zurückgegeben.

Jetzt in JS ist 2 ein wahrheitsgemäßer Wert und geht daher in den if Block. Weitere Informationen finden Sie unter Alle Falsey-Werte in JavaScript. Jeder Wert, der nicht in dieser Liste enthalten ist, wird als wahr betrachtet.

0
Rajesh 24 Feb. 2020 im 08:39