如何在不使用嵌套循环的情况下生成数组所有数对的和？

原代码错误原因 #

你的代码只遍历了数组中相邻的元素对（仅计算arr[i] + arr[i+1]），但题目要求的是所有i<j的不重复数对（每个元素与它之后的所有元素配对），因此输出结果缺失了部分数对的和。

正确实现方案 #

由于要生成的数对数量为n*(n-1)/2（n为数组长度），这个量级本身是O(n²)，因此无法做到严格的线性时间复杂度（O(n)）——毕竟结果数组的长度就是O(n²)，至少需要O(n²)的时间来生成所有元素。不过可以避免显式的嵌套for循环，用数组方法实现：

方法1：forEach + slice #

function sumTwo(arr) {
  const results = [];
  arr.forEach((num, index) => {
    // 遍历当前元素之后的所有元素，计算和并加入结果
    arr.slice(index + 1).forEach(nextNum => {
      results.push(num + nextNum);
    });
  });
  return results;
}

// 测试用例
console.log(sumTwo([5, 1, 3])); // 输出 [6, 8, 4]
console.log(sumTwo([5, 1, 3, 2])); // 输出 [6, 8, 7, 4, 3, 5]

方法2：reduce + map + concat #

function sumTwo(arr) {
  return arr.reduce((acc, num, i) => {
    // 将当前元素与后续所有元素的和拼接进结果数组
    return acc.concat(arr.slice(i + 1).map(nextNum => num + nextNum));
  }, []);
}

// 测试用例
console.log(sumTwo([5, 1, 3])); // 输出 [6, 8, 4]
console.log(sumTwo([5, 1, 3, 2])); // 输出 [6, 8, 7, 4, 3, 5]

这两种方法本质上还是O(n²)时间复杂度，但避免了显式的嵌套for循环，符合你“不使用嵌套循环”的要求。

内容的提问来源于stack exchange，提问作者Kamo