Codewars数对求和问题：O(n)实现的性能优化问询

嘿，刚学编程两周就能把双重循环的O(n²)优化到O(n)，这进步真的很亮眼！你的思路已经找对了——用空间换时间，记录已经遍历过的元素，不过当前用数组存储的方式还有可以优化的地方，尤其是在处理大范围整数的时候。

现有代码的瓶颈 #

你的代码里用了一个预先分配的数组arr来记录元素的索引，但这个方案有两个明显问题：

• 空间浪费：如果输入的整数范围很大（比如包含极小的负数或极大的正数），数组的长度会变得非常夸张，不仅占用大量内存，初始化这么大的数组也会拖慢速度。
• 偏移量计算冗余：每次访问数组都要做target-minn的计算，虽然只是简单算术，但累积起来也会影响性能。

更高效的方案：用字典替代数组 #

Python的dict（字典）查找和插入操作都是O(1)的，而且它只会存储实际出现过的元素，不需要预先分配大空间。我们可以用字典记录已经遍历过的元素及其索引，遍历的时候直接检查目标值是否在字典中即可。

优化后的代码如下：

def sum_pairs(ints, s):
    seen = {}
    for idx, num in enumerate(ints):
        target = s - num
        if target in seen:
            return [target, num]
        seen[num] = idx
    return None

为什么这个方案更快？ #

1. 空间效率更高：字典只存储已经遍历过的元素，不会为没出现过的整数预留空间，尤其适合包含极端值的测试用例。
2. 减少计算步骤：不需要计算偏移量、初始化大数组，直接通过键值对查找，逻辑更简洁，执行更快。
3. 提前返回保证最优解：一旦找到符合条件的配对就立刻返回，完全符合题目要求的“从左到右最先出现的配对”。

测试示例验证 #

• 对于sum_pairs([11, 3, 7, 5], 10)：遍历到7时，发现10-7=3已经在seen里，直接返回[3,7]，正确。
• 对于sum_pairs([4, 3, 2, 3, 4], 6)：遍历到2时，发现6-2=4已经在seen里，直接返回[4,2]，正确。

这个方案在保持O(n)时间复杂度的同时，大幅提升了空间效率和实际运行速度，应该能轻松通过所有测试用例。

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