重构嵌套的 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));

Answer 2

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

• 您当前的代码正在重复索引检查。例如，您正在循环索引 [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，则没有理由检查它。

Answer 3

你可以随着时间的推移解决这个问题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.