寻找和为给定值的一对元素
击败 O(n^2) 暴力方法
寻找和为给定值的一对元素 是 CoddyKit 上的免费 Competitive Programming Academy 课时。 这是第 2 节课，共 4 节。 你可以在下方免费阅读本课时的完整内容 — 然后在浏览器中使用内置代码编辑器和全天候 AI 导师进行实践。 这是 Competitive Programming Academy 学习路径的一部分，你的进度在网页和 CoddyKit 应用中同步。 Competitive Programming Academy 课程共包含 4 节课。
两数之和问题
给定一个数组和一个目标值，请找出两个相加后等于目标值的数。这是竞赛中最常见的热身题之一。🔍
暴力方法
最直接的做法是使用两个嵌套循环尝试每一对元素。虽然可行，但检查所有配对需要 O(n^2)，可能会慢得无法接受。
for i in range(n):
for j in range(i + 1, n):
if a[i] + a[j] == target:
return (i, j)暴力方法何时失效
当 n 接近 100000 时，O(n^2) 意味着一百亿次检查，您会遇到 TLE。题目的限制是在提示您寻找更快的方法。
先 sort，再扫描
如果先对数组执行 sort，就可以使用从两端开始的双指针在一次扫描中解决问题。排序需要 O(n log n)，之后的扫描需要 O(n)。
a.sort()
left, right = 0, len(a) - 1与目标值比较
每一步读取 a[left] + a[right]。这个数会直接决定下一步怎么移动，无需猜测。
total = a[left] + a[right]精确匹配：完成
如果总和等于目标值，您就已经找到这对数。由于只需要一个有效答案，请立即返回它。
if total == target:
return (left, right)否则进行调整
如果总和太小，就将 left 向右移动；如果太大，就将 right 向左移动。已排序的顺序保证每次移动都有帮助。
elif total < target:
left += 1
else:
right -= 1不存在配对
如果两个指针在没有匹配的情况下交错，就不存在有效配对。循环结束本身就是完整的答案。
哈希集合方案
如果必须保留原始索引，使用哈希集合会更简洁：对于每个值，检查目标值减去它的结果是否已经出现过。
seen = set()
for x in a:
if target - x in seen:
# found
pass
seen.add(x)选择您的方法
当数组已经排序或可以排序时，请使用双指针；当需要不排序也达到真正的 O(n)，或必须保留索引时，请使用哈希集合。
注意重复值
如果一个值可以与自身配对，请确保两个索引不同。快速检查 left != right 或 i != j 可以避免这个问题。
快速检查
您希望改进用于寻找目标总和配对的 O(n^2) 暴力方法。
总结
先排序，再使用双指针扫描，可以在 O(n log n) 内找到目标配对；当索引很重要时，则可以使用哈希集合在 O(n) 内完成。请根据限制条件选择方法。✅
常见问题解答
「寻找和为给定值的一对元素」课时是免费的吗？
是的 — 「寻找和为给定值的一对元素」的完整文本可在网页上免费阅读。要进行交互式练习（内置代码编辑器和全天候 AI 导师）并解锁 Competitive Programming Academy 课程的其余内容，请升级到 CoddyKit PRO。 Competitive Programming Academy 课程共包含 4 节课。
「寻找和为给定值的一对元素」这节课中我会学到什么？
击败 O(n^2) 暴力方法 你通过在浏览器中直接运行的动手代码来练习 Competitive Programming Academy，全天候 AI 导师会在你学习这节课的过程中回答你的问题。
学习 Competitive Programming Academy 需要有经验吗？
无需任何先前经验。CoddyKit 上的 Competitive Programming Academy 课程适合初学者到高级学习者，你可以从这里开始或从头开始，按照自己的节奏学习。 这是第 2 节课，共 4 节。
「寻找和为给定值的一对元素」课时需要多长时间？
大多数 CoddyKit 课程大约需要 5–10 分钟。每节课都很精短且互动，所以你能稳步进步，并在网页和应用中从离开的地方继续。
我能在这节 Competitive Programming Academy 课中编写并运行代码吗？
能。每节 Competitive Programming Academy 课都包含内置代码编辑器，你可以在浏览器中直接编写并运行真实代码，并获得即时 AI 反馈 — 无需本地设置。