为什么我这次面试的算法不是最优的？

Question

给定整数列表( l = [1,5,3,2,6]和目标t = 6 )，如果列表包含两个与目标相加的不同整数，则返回true。

在一次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

Answer 2

您可以先有两个指针(开始，结束)，开始将指向列表的开始，结束将指向列表的末尾，然后添加它们并查看它们是否等于您的目标，如果等于，则打印或添加到结果。

如果和更大，那么目标意味着将结束指针减少1，如果它等于或小于目标，则增加开始指针。

def two_Sum(l,target):
    start=0
    end=len(l)-1
    while start!=end:
        pair_sum=l[start]+l[end]
        if pair_sum==target:
            print l[start],l[end]

        if pair_sum <= target:
            start=start+1

        if pair_sum > target:
            end = end-1


l=[1,2,3,4,5,6,7,8,9,10]


two_Sum(l,9)

Answer 3

这将只在您的列表中进行一次：

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