在数组中找到总和为值的第一对数字 [英] Finding first pair of numbers in array that sum to value
问题描述
我正在尝试解决以下Codewars问题: https://www.codewars.com/kata/sum-of-pairs/train/python
Im trying to solve the following Codewars problem: https://www.codewars.com/kata/sum-of-pairs/train/python
这是我当前在Python中的实现:
Here is my current implementation in Python:
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]]
代码似乎产生正确的结果,但是输入可以包含最多包含1000000个元素的数组,因此对于大输入而言,执行会超时.我需要优化/修改代码的帮助,以便它可以处理足够大的数组.
The code seems to produce correct results, however the input can consist of array with up to 10 000 000 elements, so the execution times out for large inputs. I need help with optimizing/modifying the code so that it can handle sufficiently large arrays.
推荐答案
您的代码对于大型列表测试用例效率低下,因此会出现超时错误.相反,您可以执行以下操作:
Your code inefficient for large list test cases so it gives timeout error. Instead you can do:
def sum_pairs(lst, s):
seen = set()
for item in lst:
if s - item in seen:
return [s - item, item]
seen.add(item)
我们将这些值放入seen
中,直到找到一个产生具有seen
值之一的指定总和的值.
有关更多信息,请访问:参考链接
We put the values in seen
until we find a value that produces the specified sum with one of the seen
values.
For more information go: Referance link
这篇关于在数组中找到总和为值的第一对数字的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!