Alle Paare in einem Array, die Summe mit 10 mit durchschnittlichen/besten O (n) Laufzeitkomplexität

Question

Ich versuche, JavaScript für die Codierung zu verwenden.

Ich verwende Karten und versuche, alle Paare zu finden, die zu 10 hinzufügen. Die Paare werden jedoch nicht richtig gedruckt. Einige Paare werden gedruckt und einige Paare nicht.

<script> 
     function twoSum(nums, target_num) { 

      if(nums.length<2){ 
       return; 
      } 

      var myMap = new Map(); 
      var i; 
      var target, val; 


      for(val of nums){ 
       //New change added for the recommendation of a user below 
       //This makes the answer a little better 
       myMap.set(val,false); 
       target = target_num - val; 

       if(!myMap.has(target)){ 
        myMap.set(val,target);    
       } 

       else{    
        console.log("[" + target + "," + val +"]");   
       }       
      } 
     } 
    </script> 

My Eingang ([2,4,6,7,3,2,1,9,4,1,6,4], 10) My gewünschte Ausgang ist [4,6], [4,6], [6,4], [6,4], [7,3], [1,9], [9,1], [4,6], [6,4] Also grundsätzlich , alle Zahlen sind der Index, den ich berücksichtigen sollte. Aber die Ausgabe, die ich bekomme, ist: [4,6], [7,3], [1,9], [6,4], [9,1], [4,6], [6, 4].

Ich bin mir nicht sicher, was genau ich falsch mache. Es wäre sehr hilfreich, wenn Sie mir sagen könnten, wo ich falsch liege und wie ich mich selbst korrigieren kann. Auch mein Ziel ist es, die Laufzeit als O (n) zu haben, denkst du, dass meine Lösung das erreicht?

Ich würde Ihre Hilfe wirklich schätzen.

Vielen Dank.

Answer 1

Versuchen Sie folgendes:

function twoSum(nums, target_num) { 

    if(nums.length<2){ 
    return; 
    } 

    var myMap = new Object(); 
    var target; 

    for (var i=0; i<nums.length; i++){ 
    if (myMap[nums[i]]){ 
     myMap[nums[i]].push(i); 
    } else { 
     myMap[nums[i]] = [i]; 
    } 
    } 

    for(var i=0; i<nums.length; i++){ 
    target = target_num - nums[i]; 

    if (myMap[target]){ 
     var indexes = myMap[target].filter(j => j > i); 

     if (indexes.length > 0){ 
     console.log(
      myMap[target].filter(j => j > i) 
         .map(x => [nums[i],target]) 
     ); 
     } 
    }       
    } 
} 

console.log(twoSum([2,4,6,7,3,2,1,9,4,1,6,4],10))