python练习题,写一个方法 传进去列表和预期的value 求出所有变量得取值可能性(例如list为[1,2,3,4,5,6,12,19],value为20,结果是19+1==20只有一种可能性),要求时间复杂度为O(n)

时间:2022-10-02 16:05:36

题目:(来自光荣之路老师)
a+b==value
a+b+c=value
a+b+c+d==value
a+b+c+d+...=value
a和b....取值范围都在0-value
写一个方法 传进去列表和预期得value  求出所有变量得取值可能性

一个有顺序得数字序列  从小到大 不限制个数 序列里面随机两个数相加为value得可能性
例子[1,2,3,4,5,6,12,19] value为20
19+1==20只有一种可能性
要求时间复杂度为O(n)

代码:

#encoding=utf-8

seq=[1,19,4,16,54,32,12,56,43,87,12]
value = 20
def fun(seq,value):
    print "seq:",seq
    print "value:",value
    num=0
    try:
        list=sorted(seq)
        cur=[]
        for i in range(len(list)-1):
            data=value
           
            list1=list[:]
            list1.remove(list[i])
            #print "list:",list
            #print "list1:",list1
            #print "list[i]:",list[i]
            if (data - list[i]) in list1 and (data -list[i]) not in cur:
                print list[i],data-list[i]
                cur.append(list[i])
                cur.append(data-list[i])
                num+=1
        print "there a %s curcumstance!" %num
    except Exception,e:
        raise e

fun(seq,value)

结果:ok

D:\测试资料\python课件\Python笔记>python task_test.py
seq: [1, 19, 4, 16, 54, 32, 12, 56, 43, 87, 12]
value: 20
1 19
4 16
there a 2 curcumstance!

python练习题,写一个方法 传进去列表和预期的value  求出所有变量得取值可能性(例如list为[1,2,3,4,5,6,12,19],value为20,结果是19+1==20只有一种可能性),要求时间复杂度为O(n)