我将尝试解决以下的 Codewars 问题:https://www.codewars.com/kata/sum-of-pairs/train/python
这是我当前在 Python 中的实现:
代码似乎能够产生正确的结果,但输入可以包含多达10000000个元素的数组,因此对于大型输入而言,执行时间会超时。我需要优化/修改代码以便能够处理足够大的数组。
def sum_pairs(ints, s):
right = float("inf")
n = len(ints)
m = {}
dup = {}
for i, x in enumerate(ints):
if x not in m.keys():
m[x] = i # Track first index of x using hash map.
elif x in m.keys() and x not in dup.keys():
dup[x] = i
for x in m.keys():
if s - x in m.keys():
if x == s-x and x in dup.keys():
j = m[x]
k = dup[x]
else:
j = m[x]
k = m[s-x]
comp = max(j,k)
if comp < right and j!= k:
right = comp
if right > n:
return None
return [s - ints[right],ints[right]]
代码似乎能够产生正确的结果,但输入可以包含多达10000000个元素的数组,因此对于大型输入而言,执行时间会超时。我需要优化/修改代码以便能够处理足够大的数组。
elif x in m.keys() and x not in dup.keys()
。 - David Cian