python3面试题-一个包含n个整数的数组a,判断a中是否存在三个元素,a,b,c,使得a+b+c=0

面试题

一个包含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))

 

上一篇:新大陆NLS-EM28电梯门禁二维扫描头


下一篇:Oracle的NLS_DATE_FORMAT设置(日期格式设置)