3 sum 问题

编程算法
#1

老师请问您以下问题应如何求解：
Determine if there exists three elements in a given array that sum to the given target number. Return all the triple of values that sums to target.

Assumptions

  • The given array is not null and has length of at least 3
  • No duplicate triples should be returned, order of the values in the tuple does not matter

Examples

*A = [3, 4, 0, -1, 2, 0, 5], target = 4,return [[-1, 0, 5], [-1, 2, 3], [0, 0, 4]]

==============================================================
以下是我写的code，但是返回的时候显示的是[[-1, 0, 5], [-1, 0, 5], [-1, 2, 3], [0, 0, 4]] 请老师帮助解答，十分感谢。

def allTriples(array, target):
    array = combination_n(array,3)
    lst = list(array)
    a = []
    for i in lst:
      if sum(i) == target and i not in a:
        a.append(i)
    return a

def combination_n(array,n):
      if n == 0:
        return [[]]
      res = []
      for i in range(0,len(array)):
        m = array[i]
        remlist = array[i+1:]
        for p in combination_n(remlist,n-1):
          res.append([m]+p)
      return res
      
array = [3, 4, 0, -1, 2, 0, 5]
target = 4
result = allTriples(array,target)
print(result)
#5

从你的code来看，你是想要生成所有的三元组然后再一个一个判断，对吧。这个想法大方向上没问题（虽然不够efficient），但是你现在实现的去重操作有问题。在这个例子，你可以有这两个三元组都满足sum为4：[0, -1, 5]和[-1, 0, 5]，对吧。但是你最后存储结果的是一个list，然后你就只是简单的看一下三元组在不在这个list中。所以对于我们刚刚提到的那两个逻辑上重复的三元组，你的实现是不会认为他们是同一个的。

要在你现在的基础上fix的话，你可以先sort input然后再开始你的combination_n过程。

#6

十分感谢老师，我按照您收的先sort input 然后通过了。

1 个赞