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

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）：

^{pr2}$

Answer 2

你可以从两个指针开始（start，end），start将指向列表的开始，end将指向列表的结尾，然后添加它们，看看它是否等于目标，如果等于，则打印或添加到结果中。在

如果总和大于目标值，则意味着将结束指针减少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

最有效的方法是对每个I散列T-I[I]，然后检查每个元素

def sum2(I,T):
   h = {}
   for itm in I:
      if itm in h:
          return True
      h[T-itm] = 1
   return False