python - "do this in one pass"是什么意思？

Question

我已经开始每日代码逻辑问题并收到第一个，非常简单，但我不明白“一次性执行此操作”是什么意思。只需一行即可完成此操作？如果是的话，这个问题怎么可能？这就是问题和我的代码:

##Good morning! Here's your coding interview problem for today.
##This problem was recently asked by Google.
##Given a list of numbers and a number k, return whether any two numbers from the list add up to k.
##For example, given [10, 15, 3, 7] and k of 17, return true since 10 + 7 is 17.
##Bonus: Can you do this in one pass?
def equivalent_sum(n,list_of_n):
  for x in list_of_n:
    for y in list_of_n:
      boolean = False
      if x != y:
        if x + y == n:
          boolean = True
        print("{} + {} {}".format(x,y,boolean))
l_of_numbers = [2,3,7,10,13,17,21]
equivalent_sum(20,l_of_numbers)

Answer 1

一次 ==> O(n) 时间复杂度

您将迭代列表一次:

passed_nums = set() 
numbers = [2,3,7,10,13,17,21] 
k = 17 

def equivalent_sum(numbers):
    for num in numbers:
       diff = k - num
       if diff in passed_nums:
           return True
       passed_nums.add(num)
    return False

equivalent_sum(numbers)

或者您可以使用:

num_set = set(numbers)
any(k - e in num_set for e in numbers)  

内置函数速度更快，因为它们在 C 代码上运行