javascript - 比较数组中的值时如何提高嵌套 for 循环的性能

Question

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 循环遍历数字数组并找到一对，当求和时，它等于目标并返回它们的索引。因为它有一个嵌套的 for 循环，我相信它有 O(n^2) 或二次时间复杂度，我想知道是否有更快的方法来做到这一点。我只是想获得第一个通过的解决方案，然后对其进行改进。 😁 提前致谢!

Answer 1

创建一个对象，将每个元素映射到它的最后一个索引。然后遍历每个元素，并查看 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)。