C'è un modo per rendere questo codice più semplice?

Question

Descrizione del programma:

Dato un array di numeri interi numse un intero target, restituisce gli indici dei due numeri in modo tale che si sommino target. Si può presumere che ogni input abbia esattamente una soluzione e non si può utilizzare lo stesso elemento due volte. Puoi restituire la risposta in qualsiasi ordine.

La mia soluzione:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
  let N = nums.length;  
  for(i=0;i<=N-1;i++) {
      for(j=i+1;j<=N;j++) {
          if(nums[i] + nums[j] == target) {
              return [i,j];
          };
      };
  };  
};

Ingresso di prova:

[2,7,11,15]
9

Uscita di prova:

[0,1]

Riepilogo del test:

Solution accepted.
Runtime: 84ms

Domanda: c'è un modo per rendere questo codice più pulito usando alcune comprensioni, magari migliorandone anche il runtime? Grazie in anticipo.

Answer 1

Prestazioni Il problema più grande con la tua attuale implementazione è che lo è O(n ^ 2). Devi iterare attraverso una serie di N (N ^ 2) / 2tempi di lunghezza per trovare le corrispondenze. L'algoritmo può essere migliorato iterando una sola volta e utilizzando un Set o un oggetto durante l'iterazione per memorizzare il numero con cui il numero corrente dovrebbe essere associato per essere sommato al target.

Ad esempio, quando si esegue l'iterazione 1, con un obiettivo di 5, è possibile inserire 4nel Set, perché 1 + 4 === 5. Su ulteriori iterazioni, controllare se l'elemento su cui si sta iterando esiste nell'insieme. Se lo fa, è una corrispondenza: restituisci la coppia. Vedere in fondo alla risposta per un'implementazione.

Preferisci constrispetto alet Poiché Nnon viene riassegnato, dichiaralo con const:https://softwareengineering.stackexchange.com/questions/278652/how-much-should-i-be-using-let-vs-const-in-es6

Non creare variabili globali Dichiarare sempre le variabili prima di utilizzarle. Il tuo codice corrente con for(i=0;i<=N-1;i++)e for(j=i+1;j<=N;j++) {crea implicitamente variabili ie globali j. Questo è inelegante e può portare a bug confusi se la funzione viene chiamata di nuovo prima del completamento della sua prima chiamata. (Considera anche l'aggiunta di spazi tra gli operatori per la leggibilità). Ti piacerebbe fare:

for (let i = 0; i < N; i++) {

Nota l'uso di i < N, not i <= N; poiché Nè la lunghezza, nums[N]sarà undefined, quindi non dovresti iterare su di essa.

Usa l'uguaglianza rigorosa Non usare ==: ha molte regole strane con la coercizione del tipo. Anche se sei sicuro che i tipi di operandi siano gli stessi, per renderlo più chiaro per i lettori a colpo d'occhio, meglio evitarlo e usare ===o !==invece.

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
const twoSum = function(nums, target) {
  // Key: Number which, if found, matches the number at the index value
  // eg: { 3 => 6 }: if 3 is found later, it'll be a match with the number at index 6
  const indexByPair = new Map();
  const { length } = nums;
  for (let i = 0; i < length; i++) {
    if (indexByPair.has(nums[i])) {
      return [indexByPair.get(nums[i]), i];
    }
    indexByPair.set(target - nums[i], i);
  }
};
console.log(twoSum([2,7,11,15], 9));