本文详解如何正确实现数组中任意两个不同元素的两两求和，生成包含所有组合和的数组，并澄清关于线性时间复杂度的常见误解。
本文详解如何正确实现数组中任意两个不同元素的两两求和，生成包含所有组合和的数组，并澄清关于线性时间复杂度的常见误解。
要生成一个数组中所有不重复、无自加的两两元素之和（即对所有满足 i < j 的索引对 (i, j)，计算 arr[i] + arr[j]），核心在于准确枚举所有组合——这本质上是一个组合生成问题，而非线性扫描问题。
为什么无法达到 O(n) 时间复杂度？
题目中提出“不用嵌套循环以维持线性时间复杂度”，这是一个关键误区。对于长度为 n 的数组，两两不重复组合的数量为 C(n,2) = n×(n−1)/2，即 Ω(n²) 个结果。即使仅输出这些和，也必须执行至少 O(n²) 次加法与写入操作。因此，任何正确解法的时间复杂度下界均为 O(n²)，不可能优化至 O(n) 或 O(n log n)。
正确实现：双指针式嵌套循环（推荐）
最清晰、高效且符合语义的实现是使用外层循环控制第一个元素索引 i，内层循环从 i+1 开始遍历剩余元素：
function sumTwo(arr) {
const results = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
results.push(arr[i] + arr[j]);
}
}
return results;
}
// 示例验证
console.log(sumTwo([5, 1, 3])); // [6, 8, 4]
console.log(sumTwo([5, 1, 3, 2])); // [6, 8, 7, 4, 3, 5]该实现：
- ✅ 覆盖全部 i < j 组合，无遗漏、无重复；
- ✅ 不包含 arr[i] + arr[i]（即跳过自加）；
- ✅ 输出顺序固定（按字典序索引对），但题目明确“顺序无关”，故完全合规；
- ✅ 空间复杂度 O(n²)，与输出规模匹配，无可避免。
常见错误分析
原始尝试中仅累加相邻元素 arr[i] + arr[i+1]，实质是计算滑动窗口大小为 2 的连续和，得到的是 [5+1, 1+3] = [6, 4]，遗漏了 5+3，因此逻辑不符需求。
进阶说明：能否用数学技巧“绕过”嵌套循环？
有人考虑预计算前缀和、哈希映射或 FFT 加速，但需注意：
- 前缀和用于区间求和，不适用于离散两两配对；
- 哈希无法减少组合枚举量；
- FFT 可用于多项式乘法（间接求和频次），但无法直接输出所有具体和值，且常数巨大、不实用。
因此，双重循环不是缺陷，而是问题本质决定的最优表达。
总结
- 目标问题必然要求 O(n²) 时间与空间；
- 推荐使用 for (i=0; i<n; i++) { for (j=i+1; j<n; j++) { ... } } 模式，简洁、可读、无冗余；
- 避免混淆“相邻求和”与“所有组合求和”；
- 在实际工程中，若 n 较大（如 >10⁴），应评估是否真需全部结果——有时可改用延迟生成器（Generator）或流式处理，但复杂度不变。
正确理解问题规模边界，比强行追求不存在的“线性解法”更重要。
