как улучшить производительность вложенных циклов при сравнении значений в массиве - PullRequest
Новая
       10

как улучшить производительность вложенных циклов при сравнении значений в массиве

2 голосов
/ 15 февраля 2020 
var twoSum = function(nums, target) {
  for(let i = 0; i < nums.length; i++){
    for(let j = i + 1; j < nums.length; j++){
      if(nums[i] + nums[j] === target){
        return [nums.indexOf(nums[i]), nums.lastIndexOf(nums[j])]
      }
    }
  }
}
function([3,5,3,7,2], 9) //It should return [3, 4] since 7 + 2 = 9

Это функция Javascript, она перебирает массив чисел с вложенными циклами for и находит пару, которая при суммировании равна цели и возвращает их индексы. Поскольку он имеет вложенность для l oop, я считаю, что он имеет сложность времени O (n ^ 2) или квадратичности c, и мне было интересно, есть ли более быстрый способ сделать это. Я просто пытаюсь найти решение для первого прохода, а затем улучшить его. ? Заранее спасибо!

Ответы [ 2 ]

5 голосов
/ 15 февраля 2020

Создайте объект, который сопоставляет каждый элемент с его последним индексом. Затем l oop по каждому элементу и посмотрите, есть ли target - element в объекте с другим индексом. 

function twoSums(nums, target) {
  const last_index = {};
  nums.forEach((num, i) => last_index[num] = i);
  for (let i = 0; i < nums.length; i++) {
    const diff = target - nums[i];
    if (diff in last_index && last_index[diff] != i) {
      return [i, last_index[diff]];
    }
  }
}

const list = [3,5,3,7,2];
console.log(twoSums(list, 9));
console.log(twoSums(list, 6));
console.log(twoSums(list, 15));

Поиск свойства объекта - это O (1), поэтому этот алгоритм - O (n).

2 голосов
/ 15 февраля 2020

Вы можете использовать вложенные map(): 

var twoSum = (nums, target)=> {
  //  map trough list for first number
  nums.map(
  	(val1, index1)=>
    {
      // map through list again for second number to compare to number returned from first map at each instance
      nums.map((val2, index2) =>
      {
      //  Ensure that index1 and index2 are not the same before you compare
        if(index1 != index2 && (val1 + val2 === target))
        {
          alert([index1, index2]);
          return [index1, index2];
        }
      });
    }
  );
}

twoSum([3,5,3,7,2], 9) //It should return [3, 4] since 7 + 2 = 9

Примечание: помните, что это не будет l oop по всем пунктам, если совпадение не было найдено. Как только совпадение найдено, функция возвращается и завершается.

...