JavaScript:使用高阶函数编写此解决方案

Question

我解决了一个问题，给你一个数字数组和一个目标总和，你的工作是找到一对总和等于目标数字的数字。这是我使用简单的嵌套 for 循环的解决方案:

function findPairForSum(integers, target) {
  var output = [];

  for (var i = 0; i < integers.length; i++) {

    for (var j = 0; j < integers.length; j++) {

      if (i !== j && integers[i] + integers[j] === target) {
        output.push(integers[i], integers[j]);
        return output;
      }
    }
  }
  return 'not possible';
}

findPairForSum([3, 34, 4, 12, 5, 2], 9);  // --> [4, 5]

我的问题是，是否有更简洁的方法来使用高阶函数(可能是 forEach？)来编写此解决方案

这是我使用 forEach 的尝试:

function findPairForSum(integers, target) {
  var output = [];

  integers.forEach(function(firstNum) {
    integers.forEach(function(secondNum) {

      if (firstNum + secondNum === target) {
        output.push(firstNum, secondNum);
      }
    })
  })

  if (output === []) {
    return 'not possible'; 
  }  
  return output;
}

findPairForSum([3, 34, 4, 12, 5, 2], 9); // --> [ 4, 5, 5, 4 ]

我尝试在两次推送后返回，但没有返回任何内容。所以相反，我把返回放在最后。

为什么在最初的两次推送后它不返回？我希望它停在那里，只推送两个数字。相反，通过将 return 放在最后，它推出了 4 个数字。它应该是 [4,5] 但我得到的是 [4,5,5,4]。

任何建议和帮助将不胜感激!

Answer 1

假设我们有以下一组数字，我们必须找到总和为 9 的 2 个数字的子集:

Numbers: 4, 5, 6

您当前的代码使用 i 和 j 从 0 迭代到 length。这意味着以下迭代符合条件:

Indices: 0, 1, 2
Numbers: 4, 5, 6   //        (i)          (j)
----------------   //         ↓            ↓
         i  j      // Numbers[0] + Numbers[1] === 9
         j  i      // Numbers[1] + Numbers[0] === 9

如您所见，数字 4 和 5 在 2 次迭代中匹配了两次:

• i === 0 && j === 1
• i === 1 && j === 0

您可以通过确保满足一个简单条件来避免这种情况:

j 必须始终大于 i

这个条件可以通过在内部 for 循环中用 i + 1 初始化 j 来满足:

for (var i = 0; i < integers.length; i++) {
    for (var j = i + 1; j < integers.length; j++) {
        // ...
    }
}

这样，当 i 为 1 时，j 永远不会为 0，因为内部的 for 循环将在 i 再次递增之前运行完成。一旦发生这种情况，就会创建一个全新的内部 for 循环，其中 j 再次设置为 i + 1。下图是结果:

Indices: 0, 1, 2
Numbers: 4, 5, 6
----------------
         i  j
         X  i     // ← j can never be 0 if (i === 1),
                  //   so the same set is never evaluated twice.

换句话说，最多只检查以下i和j的组合:

Indices: 0, 1, 2
----------------
         i  j
         i     j
            i  j

is there a cleaner way to write this solution using higher order functions (perhaps forEach?)

对于您的用例，for 循环实际上是一个很好的解决方案。它们允许您提早突破 - 在您第一次找到一对有效数字之后。另一方面，forEach 或其他数组迭代器函数将始终继续，直到访问所有集合索引。

您实际上在第一个示例中使用语句 return output;

当您对具有多个有效集合的一组数字使用 forEach 时，您总是会取回所有涉及的数字:

Indices: 0, 1, 2, 3
Numbers: 4, 5, 6, 3    //        (i)          (j)
-------------------    //         ↓            ↓
         i  j          // Numbers[0] + Numbers[1] === 4 + 5 === 9
               i  j    // Numbers[2] + Numbers[3] === 6 + 3 === 9

forEach、map、reduce 等不允许您提前中断。 以下代码段演示了上图的这个问题:

function findPairForSum(integers, target) {
    var output = [];

    integers.forEach(function(firstNum, i) {
    
        // slice(i + 1) has the same effect as for (var j = i + 1; ...)
        integers.slice(i + 1).forEach(function(secondNum, j) {
        
            if (firstNum + secondNum === target) {
            
                // There is no way here to stop the iteration of either
                // forEach call... T_T
                output.push(firstNum, secondNum);
            }
        });
    })

    if (output.length) {
        return output;
    }

    return 'not possible';
}

console.log(findPairForSum([4, 5, 6, 3], 9)); // --> [4, 5, 6, 3]

这就是为什么我强烈建议针对此特定用例坚持使用 for 循环。使用 for 循环，只要遇到一组有效数字，您就可以简单地返回:

function findPairForSum(integers, target) {
    for (var i = 0; i < integers.length; i++) {
        for (var j = i + 1; j < integers.length; j++) {
            if (integers[i] + integers[j] === target) {
                return [integers[i], integers[j]];
            }
        }
    }

    return 'not possible';
}

console.log(findPairForSum([4, 5, 6, 3], 9)); // --> [4, 5]