Existe uma maneira de tornar este código mais simples?

Question

Descrição do Programa:

Dado um array de inteiros numse um inteiro target, retorna os índices dos dois números de forma que eles se somam target. Você pode presumir que cada entrada teria exatamente uma solução e não pode usar o mesmo elemento duas vezes. Você pode retornar a resposta em qualquer ordem.

Minha solução:

/**
 * @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 teste:

[2,7,11,15]
9

Resultado do teste:

[0,1]

Resumo do teste:

Solution accepted.
Runtime: 84ms

Pergunta: existe uma maneira de fazer este código parecer mais organizado usando algumas compreensões, talvez também melhorando seu tempo de execução? Agradeço antecipadamente.

Answer 1

Desempenho O maior problema com sua implementação atual é que é O(n ^ 2). Você deve iterar através de uma matriz de N (N ^ 2) / 2tempos de comprimento para encontrar correspondências. O algoritmo pode ser melhorado iterando apenas uma vez e usando um Set ou um objeto ao iterar para armazenar com qual número o número atual teria que ser emparelhado para somar ao destino.

Por exemplo, ao iterar 1, com um destino de 5, você pode colocar 4no Conjunto, porque 1 + 4 === 5. Em outras iterações, verifique se o elemento que está sendo iterado existe no Conjunto. Se sim, é uma combinação: devolva o par. Veja o final da resposta para uma implementação.

Prefere constmaislet Desde Nnão está sendo transferido, declará-lo com const:https://softwareengineering.stackexchange.com/questions/278652/how-much-should-i-be-using-let-vs-const-in-es6

Não crie variáveis ​​globais Sempre declare as variáveis ​​antes de usá-las. Seu código atual com for(i=0;i<=N-1;i++)e for(j=i+1;j<=N;j++) {é implicitamente criando mundial ie jvariáveis. Isso é deselegante e pode levar a erros confusos se a função for chamada novamente antes de sua primeira chamada ser concluída. (Considere também adicionar espaços entre os operadores para facilitar a leitura). Você gostaria de fazer:

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

Observe o uso de i < N, não i <= N; uma vez que Né o comprimento, nums[N]será undefined, portanto, você não deve iterar sobre ele.

Use igualdade estrita Não use ==- tem muitas regras estranhas com coerção de tipo. Mesmo se você tiver certeza de que os tipos de operandos são os mesmos, para tornar mais claro para os leitores à primeira vista, é melhor evitá-lo e usar ===ou em !==vez disso.

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