javascript - 重构嵌套 For 循环

Question

说明

给定一个整数数组，返回两个数字的索引，使它们加起来等于特定目标。

您可以假设每个输入只有一个解决方案，并且您可能不会两次使用相同的元素。

示例

Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9, return [0, 1].

我如何重构它以消除嵌套的 for 循环？我想降低时间复杂度。

代码

const twoSum = function(nums, target) {
    for(let i in nums){
      for(let j in nums) {
        if(nums[i] + nums[j] === target && nums[i] != nums[j]) {
            return [i, j];
        }
      }
    }
};

console.log(twoSum([2, 7, 11, 15], 9));

Answer 1

您可以将每个元素与目标的差异保存在一个对象中，结果作为键，索引作为值。这将检查对象内部是否存在元素，而无需循环遍历整个内容。在不同的循环中，检查数组元素是否存在于对象中，如果存在，那么你就得到了这对。附加条件是防止将元素与其自身进行比较。

const twoSum = function(nums, target) {  
  const temp = {};
  for(let i=0; i<nums.length; i++) {
    temp[target - nums[i]] = i;
  }

  for(let i=0; i<nums.length-1; i++) {
    if(temp[nums[i]] && temp[nums[i]] !== i) {
      return [i, temp[nums[i]]]
    }
  }
};

console.log(twoSum([2, 11, 7, 17], 9));
console.log(twoSum([1, 3, 4, 2], 6));