面试题

一个包含n个整数的数组a，判断a中是否存在三个元素，a，b，c，使得a+b+c=0?

找出所有和为0并且不重复的三元组。不可包含重复的三元组。

如;a=[-1,0,1,2,-1,-4]

输出：[[-1,-1,2],[-1,0,1]]

如：a=[]

输出[]

如：a=[1,2]

输出[]

思考：

实现：假如a的数组有6位数字，3位数字组合在一起，组合的情况就有C63=6*5*4/(1*2*3)=20种情况，

　　这20种情况，可能有重复的；此时，我们需要去重；

　　　　方式1:先判断符合的数组，再去重；和为0的数组，排序后，判断是否在最终结果数列中，同时往最终结果数列中追加的数列需要排序；

　　　　方式2：先去重，再判断符合的数组；可以通过set去重的方式实现，set中不可包含数组、可包含元组，同时每个元组中的数据也需要排序；

a=[1,2,3]
b=[[2,1,3]]
print(a in b) #False
a=[1,2,3]
b=[[1,2,3]]
print(a in b) #True

 

代码实现：

a=[-1,0,1,2,-1,-4]
nl=[]
lnl=[]
num=len(a)
for i in range(num):
    for j in range(i+1,num):
        for k in range(j+1,num):
            nl.append(tuple(sorted([a[i],a[j],a[k]]))) #这里需要排序，然后使用set去重；set集合里只能包含元组、不能包含数组
print(len(nl),nl)
nls=set(nl) #去重；
print(len(nls),nls)
for i in nls:
    if i[0]+i[1]+i[2]==0:
        lnl.append(list(i))
print(lnl)

运行结果：

20 [(-1, 0, 1), (-1, 0, 2), (-1, -1, 0), (-4, -1, 0), (-1, 1, 2), (-1, -1, 1), (-4, -1, 1), (-1, -1, 2), (-4, -1, 2), (-4, -1, -1), (0, 1, 2), (-1, 0, 1), (-4, 0, 1), (-1, 0, 2), (-4, 0, 2), (-4, -1, 0), (-1, 1, 2), (-4, 1, 2), (-4, -1, 1), (-4, -1, 2)]
14 {(-1, -1, 2), (-4, 0, 2), (-4, 1, 2), (-1, 0, 2), (-1, -1, 1), (-4, -1, 2), (0, 1, 2), (-4, -1, -1), (-4, 0, 1), (-1, -1, 0), (-1, 0, 1), (-1, 1, 2), (-4, -1, 1), (-4, -1, 0)}
[[-1, -1, 2], [-1, 0, 1]]

写成函数的格式：

def sums(numl,sum=0):
    nl=[]
    lnl=[]
    num=len(a)
    if num<3:
        return []
    for i in range(num):
        for j in range(i+1,num):
            for k in range(j+1,num):
                nl.append(tuple(sorted([a[i],a[j],a[k]]))) 
    # print(len(nl),nl)
    nls=set(nl) #去重；
    # print(len(nls),nls)
    for i in nls:
        if i[0]+i[1]+i[2]==sum:
            lnl.append(list(i))
    return lnl

a=[-1,0,1,2,-1,-4]
# a=[]
print(sums(a))