本文详解如何正确实现数组中任意两个不同元素的两两求和，生成包含所有组合和的数组，并澄清关于线性时间复杂度的常见误解。
本文详解如何正确实现数组中任意两个不同元素的两两求和，生成包含所有组合和的数组，并澄清关于线性时间复杂度的常见误解。
要生成一个数组中所有不重复、无自加的两两元素之和（即对所有满足 i 组合生成问题，而非线性扫描问题。
为什么无法达到 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 <p>该实现：</p><div class="aritcle_card flexRow artxards">
<div class="artcardd flexRow">
<a class="aritcle_card_img" rel="nofollow" href="/ai/2906" title="Product Manager Skills"><img
src="https://img.php.cn/upload/ai_manual/001/246/273/177985659219253.png" alt="Product Manager Skills" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
<div class="aritcle_card_info flexColumn">
<a rel="nofollow" href="/ai/2906" title="Product Manager Skills" class="overflowclass">Product Manager Skills</a>
<p class="overflowclass">一款AI工具，主要用于产品经理技能，适用于 Claude Code、Codex、Cursor 和 Windsurf。涵盖 SaaS 指标诊断、PRD 评审、路线图规划、需求探索，以及面向产品经理的职业转型辅导等，适合需要提升相关任务效率的用户。</p>
</div>
<a rel="nofollow" href="/ai/2906" title="Product Manager Skills" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
</a>
</div>
</div>
- ✅ 覆盖全部 i
- ✅ 不包含 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 较大（如 >10⁴），应评估是否真需全部结果——有时可改用延迟生成器（Generator）或流式处理，但复杂度不变。
正确理解问题规模边界，比强行追求不存在的“线性解法”更重要。
