python - 为什么我这次采访的算法不是最佳方法？

Question

Given a list of integers, l = [1,5,3,2,6] and a target t = 6, return true if the list contains two distinct integers that sum to the target

我在 Python 技术面试中被问到这个问题，导致我没有通过。我的回答是:

def two_Sum(l, target):
  for num in l:
    for secondNum in l:
      if num != secondNum:
        if num + secondNum == target:
          return True

我得到的反馈是我的解决方案“不是最佳的”。请帮助我理解为什么这不是最佳解决方案，并详细解释对于这种情况什么是最佳解决方案!

Answer 1

您的解决方案有一个迭代列表的嵌套循环，这意味着它的时间复杂度为 O(n^2) - 空间复杂度为 O(1)，因为您不这样做迭代期间不需要存储任何数据。

像这样降低到 O(n) 时间复杂度是可能的，但代价是增加到 O(n) 空间复杂度:

def two_sum(l, target):
    s = set(l)
    for n in l:
        delta = target - n
        if delta != n and delta in s:
            return True
    return False

作为一个微小的改进，您甚至可以避免遍历整个列表，但它仍然是O(n):

def two_sum(l, target):
    seen = set()
    for n in l:
        delta = target - n
        if delta != n and delta in seen:
            return True
        seen.add(n)
    return False