重构嵌套 For 循环

Question

说明

给定一个整数数组，return 两个数字的索引，使它们加起来达到特定目标。

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

例子

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));

Answer 2

你可以用O(n)时间解决这个问题。这种方法要解决的条件是数组必须排序

let twosum = (arr, x) => {
  let s = 0,
    e = arr.length - 1;
  let loc = [];

  while (s < e) {
    if (arr[s] + arr[e] === x) {
      loc.push([s,e]);
      s++;
      e--;
    } else if (arr[s] + arr[e] < x) {
      s++;
    } else {
      e--;
    }
  }

  return loc;
};

console.log(twosum([1, 2, 3, 4, 5, 7, 8], 9));
console.log(twosum([2, 7, 11, 15], 9));

这背后的算法如果有人感兴趣的话：

1.   Set s value as 0
2.   Set e value as last index say (arr.length - 1)
3.   While s is less than e i.e not pass one another
4.   Check if arr[s] + arr[e] === x then we find it.
4.1. increment s value by 1 as there is no possibility to find any combination before the current s value
4.2. decrement e value by 1 as there is no possibility to find any combination after the current e value
4.3. collect the indexes where the match found.
5.   If arr[s] + arr[e] < x
5.1  increment s as there is no possibility to find any combination before the current s value. But there still has the possibility for the e value to get a match.
6.   If arr[s] + arr[e] > x
6.1  decrement e as there is no possibility to find any combination after the current e value. But there still has the possibility for the s value to get a match.

Answer 3

由于这似乎是作业，我会提出一些建议，但不会给出完整的解决方案：

您当前的代码正在重复索引检查。例如，您正在遍历索引 [0,1] 和 [1,0]，因为 a+b = b+a，它们的总和始终相同。相反，我建议 i 的循环从 0 到 len-1，j 的循环从 i+1 到 len-1。这样你就永远不会重复检查。
您当前的部分检查包括条件 nums[i] != nums[j]，但您的问题并未说明数组中的两个值不能相同。是否可以使用 toSum([1, 4, 4], 8) 这样的值来调用此函数，使得 4+4=8？如果是这样，那么您可以删除 nums[i] != nums[j] 检查以节省时间。
不清楚提供的数组是否已排序。如果不是，那么您可以创建一个跟踪变量来说明您已经检查过的值，并防止在未来的迭代中检查它们。例如，如果您已经将值 4 与数组中的所有其他值进行了比较，但没有找到解决方案，那么如果您稍后在数组中遇到 4，则没有理由检查它。

重构嵌套 For 循环

Refactor Nested For Loop

javascript

arrays

for-loop

nested-loops