Codewars列表配对求和:memoization解法超时问题与优化咨询
最早匹配两数和问题的思路验证与实现优化
对原有遍历顺序的判断
- 你设计的按右索引从小到大、依次匹配之前所有左元素的遍历顺序,完全匹配题目要求:所有和为目标值的数对中,第二个元素索引最小的那一对,就是题目要求的“按出现顺序最早出现”的结果,这个遍历思路本身没有逻辑错误。
现有代码的超时根因
- 核心性能硬伤是双重循环带来的O(n²)时间复杂度:每遍历到一个新元素,都要从头循环比对它之前的所有元素,当测试用例的列表规模较大时,总计算量会随列表长度平方级增长,必然触发超时限制。
- 你引入的“统计数字出现次数、过滤出现超过两次的元素”的memo逻辑,并没有参与查找过程,既没有减少内层循环的计算量,还额外增加了字典读写的开销,对性能提升没有实际帮助。
- 鲁棒性缺陷:代码开头直接读取
ints[0]写入字典,遇到空列表、长度为1的列表的测试用例时,会直接触发索引越界错误。
通用高效解法思路
- 优化核心是把内层的逐元素循环查找,替换为O(1)时间复杂度的哈希查找,将整体时间复杂度压缩到O(n)
- 具体执行逻辑:
- 初始化空哈希集合,存储已经遍历过的元素
- 按索引顺序从头到尾遍历列表的每个元素(记为当前值
num) - 计算当前元素对应的互补匹配值:
complement = s - num - 直接检查互补值是否在已存储的哈希集合中:
- 如果存在,直接返回
[complement, num]——这个结果就是符合要求的最早匹配对:按顺序遍历到当前位置时,找到的配对的右元素索引,是所有可能匹配中最小的,完全符合题目排序要求 - 如果不存在,把当前
num加入哈希集合,继续遍历下一个元素
- 如果存在,直接返回
- 遍历完整个列表都未找到匹配值时,返回
None
- 该方法的匹配结果和你原本设计的遍历顺序完全等价,但省掉了内层逐元素比对的循环,哪怕是数万长度的列表,也能在单次遍历内完成查找,不会触发超时。
内容的提问来源于stack exchange,提问作者Jacek Fanslau
相关产品推荐
相关产品推荐

