¿Hay alguna forma de simplificar este código?

Question

Descripción del programa:

Dada una matriz de números enteros numsy un número entero target, devuelve índices de los dos números de manera que sumen target. Puede suponer que cada entrada tendría exactamente una solución y no puede usar el mismo elemento dos veces. Puede devolver la respuesta en cualquier orden.

Mi solución:

/**
 * @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];
          };
      };
  };  
};

Entrada de prueba:

[2,7,11,15]
9

Salida de prueba:

[0,1]

Resumen de la prueba:

Solution accepted.
Runtime: 84ms

Pregunta: ¿hay alguna manera de hacer que este código se vea más ordenado usando algunas comprensiones, quizás también mejorando su tiempo de ejecución? Gracias de antemano.

Answer 1

Rendimiento El mayor problema con su implementación actual es que lo es O(n ^ 2). Tienes que recorrer una serie de N (N ^ 2) / 2tiempos de duración para encontrar coincidencias. El algoritmo se puede mejorar iterando solo una vez y usando un Conjunto o un objeto al iterar para almacenar con qué número tendría que emparejarse el número actual para sumar el objetivo.

Por ejemplo, al iterar 1, con un objetivo de 5, podría poner 4en el Conjunto, porque 1 + 4 === 5. En iteraciones posteriores, compruebe si el elemento sobre el que se itera existe en el Conjunto. Si es así, es una coincidencia: devuelve el par. Consulte la parte inferior de la respuesta para ver una implementación.

Preferir constsobrelet Dado Nque no se va a reasignar, declararlo con const:https://softwareengineering.stackexchange.com/questions/278652/how-much-should-i-be-using-let-vs-const-in-es6

No cree variables globales Siempre declare las variables antes de usarlas. Su código actual con for(i=0;i<=N-1;i++)y for(j=i+1;j<=N;j++) {está creando implícitamente variables globales iy j. Esto es poco elegante y puede generar errores confusos si se vuelve a llamar a la función antes de que se complete su primera llamada. (También considere agregar espacios entre operadores para facilitar la lectura). Querrías hacer:

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

Tenga en cuenta el uso de i < N, no i <= N; ya que Nes la longitud, nums[N]será undefined, por lo que no debe iterar sobre ella.

Use igualdad estricta No use ==- tiene muchas reglas extrañas con coerción de tipos. Incluso si está seguro de que los tipos de operandos son los mismos, para que sea más claro para los lectores de un vistazo, es mejor evitarlo y usar ===o en su !==lugar.

/**
 * @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));