Python: 每日一题 43

ooxx7788

给定一个由数值组成的列表(array)和一个整数(interger),返回列表中相加之和等于整数的两个数。
列表长度最长为1000万，用时不超过12秒(好像是1.2秒,还是7秒,好烦没有给出明确时间)。

由于这个编辑器的关系,我实在没有办法正常对齐,所以你们就将就着看吧.

sum_pairs([11, 3, 7, 5],         10)
#                 ^-^      3 + 7 = 10
== [3, 7]

sum_pairs([4, 3, 2, 3, 4],         6)
#           ^---^         4 + 2 = 6, index: 0, 2 *
#             ^---^      3 + 3 = 6, index: 1, 3
#                 ^---^   2 + 4 = 6, index:  2, 4
#  * 返回整体最早出现的答案
== [4, 2]

sum_pairs([0, 0, -2, 3], 2)
#  没有可以相加成2的组合.
== None

sum_pairs([10, 5, 2, 3, 7, 5],         10)
#                 ^--------^   5 + 5 = 10, index: 1, 5
#                    ^-^      3 + 7 = 10, index: 3, 4 *
#  * 返回整体最早出现的答案
== [3, 7]

测试代码:
先更新一些test.py

def assert_equals(func, target, *args):
    if func == target:
        print('Success！')
    else:
        print('Fail!{0} not equals {1}'.format(func, target))
        print(*args)

l1 = [1, 4, 8, 7, 3, 15]
l2 = [1, -2, 3, 0, -6, 1]
l3 = [20, -13, 40]
l4 = [1, 2, 3, 4, 1, 0]
l5 = [10, 5, 2, 3, 7, 5]
l6 = [4, -2, 3, 3, 4]
l7 = [0, 2, 0]
l8 = [5, 9, 13, -3]

test.assert_equals(sum_pairs(l1, 8), [1, 7], "Basic: %s should return [1, 7] for sum = 8" % l1)
test.assert_equals(sum_pairs(l2, -6), [0, -6], "Negatives: %s should return [0, -6] for sum = -6" % l2)
test.assert_equals(sum_pairs(l3, -7), None, "No Match: %s should return None for sum = -7" % l3)
test.assert_equals(sum_pairs(l4, 2), [1, 1], "First Match From Left: %s should return [1, 1] for sum = 2 " % l4)
test.assert_equals(sum_pairs(l5, 10), [3, 7],
                   "First Match From Left REDUX!: %s should return [3, 7] for sum = 10 " % l5)
test.assert_equals(sum_pairs(l6, 8), [4, 4], "Duplicates: %s should return [4, 4] for sum = 8" % l6)
test.assert_equals(sum_pairs(l7, 0), [0, 0], "Zeroes: %s should return [0, 0] for sum = 0" % l7)
test.assert_equals(sum_pairs(l8, 10), [13, -3], "Subtraction: %s should return [13, -3] for sum = 10" % l8)

游客，如果您要查看本帖隐藏内容请回复

余欲渔

def sum_pairs(array=[11,3,7,5],interger=10):
    jg=[]
    njg=[]
    l=len(array)
    x=1
    for i in range(l-1,0,-1):
        if i<2:x=0
        for j in range(i-1,-1,-1):
            if array[i]+array[j]==interger:
                jg=[array[j],array[i],j,i]
    if x:
        njg=sum_pairs(array[:jg[3]],interger)
    if jg==[]:
        return []
    elif njg==[]:
        return str(jg[0])+'+'+str(jg[1])+'='+str(interger)+',index:'+str(jg[2])+','+str(jg[3])
    else:
        return str(njg[0])+'+'+str(njg[1])+'='+str(interger)+',index:'+str(njg[2])+','+str(njg[3])

print(sum_pairs([10,5,2,3,7,5],10))

ooxx7788

余欲渔 发表于 2017-5-11 10:42

([20, -13, 40], -7)
不能返回正确的结果.
查明白了,应该返回None,但是你返回的是[]。到不是程序问题。

冬雪雪冬

没有搞清规则：？

sum_pairs([10, 5, 2, 3, 7, 5],         10)
#                 ^--------^   5 + 5 = 10, index: 1, 5
#                    ^-^      3 + 7 = 10, index: 3, 4 *
#  * 虽然整体最早出现的答案
== [3, 7]

ooxx7788

冬雪雪冬 发表于 2017-5-11 13:38
没有搞清规则：？

好像打错字了，应该是返回整体最早出现的答案。
简单说，其实就是答案的后一个数字排在前面的优先。

冬雪雪冬

ooxx7788 发表于 2017-5-11 14:00
好像打错字了，应该是返回整体最早出现的答案。
简单说，其实就是答案的后一个数字排在前面的优先。

明白了。

def sum_pairs(list1, num):
    for i in range(1, len(list1)):
        for j in range(i):
            if list1[i] + list1[j] == num:
                return [list1[j], list1[i]]

ooxx7788

冬雪雪冬 发表于 2017-5-11 14:08
明白了。

从计算角度而言，结果这样肯定是没有问题的。
但是时间上是完成不了的。两层循环肯定超时。

冬雪雪冬

ooxx7788 发表于 2017-5-11 14:32
从计算角度而言，结果这样肯定是没有问题的。
但是时间上是完成不了的。两层循环肯定超时。

这样改，不知效率能否提高。

def sum_pairs(list1, num):
    for i in range(1, len(list1)):
        if list1[:i].count(num - list1[i]):
            return [num - list1[i], list1[i]]

ooxx7788

不对不对,原来刚刚是我网络卡了,才通过的!
依然是

Process was terminated. It took longer than 12000ms to complete

但是我觉得你这样好像已经效率很高了!
这些要求时间,和代码长度的题目贼烦.

ooxx7788

冬雪雪冬 发表于 2017-5-11 15:09
这样改，不知效率能否提高。

不过我刚刚偷偷瞄了一眼答案,我就明白了,不是题目设计的问题.
确实是有方法可以提高速度的.

冬雪雪冬

ooxx7788 发表于 2017-5-11 15:51
不过我刚刚偷偷瞄了一眼答案,我就明白了,不是题目设计的问题.
确实是有方法可以提高速度的.

没有更好的想法，用set是否快点。

def sum_pairs(list1, num):
    for i in range(1, len(list1)):
        if num - list1[i] in set(list1[:i]):
            return [num - list1[i], list1[i]]

ooxx7788

冬雪雪冬 发表于 2017-5-11 16:37
没有更好的想法，用set是否快点。

没错，就是set。
还是要服你，我反正是没想起来。

badaoqingchen

冬雪雪冬 发表于 2017-5-11 15:09
这样改，不知效率能否提高。

if list1[:i].count(num - list1[i])
请问这一句怎么解释啊，求教

冬雪雪冬

badaoqingchen 发表于 2017-5-11 16:53
if list1[:i].count(num - list1)
请问这一句怎么解释啊，求教

这是看num - list1的值是否在list1[:i]中，如果不在返回0
为什么是list1[:i]呢？假如第一个数在列表的第5位，只看0~4位就可以了。

冬雪雪冬

ooxx7788 发表于 2017-5-11 16:43
没错，就是set。
还是要服你，我反正是没想起来。

我不知道是题目哪个网站的，请帮我测试一下，看看速度。

badaoqingchen

冬雪雪冬 发表于 2017-5-11 16:58
这是看num - list1的值是否在list1[:i]中，如果不在返回0
为什么是list1[:i]呢？假如第一个数在列表的第 ...

水土都不服，就服你
明白了，这个是判断count( )的返回值。
我感觉for循环已经挺快的了啊，为什么用count（） 和 set（）会更快呢？
内部判断的时候，不管set还是count不应该都是用for循环遍历吗

冬雪雪冬

badaoqingchen 发表于 2017-5-11 17:06
水土都不服，就服你
明白了，这个是判断count( )的返回值。
我感觉for循环已经挺快的了啊， ...

我不是很能理解其中的原因，一般教科书上说，集合是hash散列，查找的速度原快于列表元组，特别是数据量大时。

ooxx7788

冬雪雪冬 发表于 2017-5-11 16:59
我不知道是题目哪个网站的，请帮我测试一下，看看速度。

还是不行，超时。
这是codewars  5kyu的题目, 这个级别的题目会出现对时间或代码量的限制性要求.
单论逻辑而言, 这个题目本身到也不难.
原文地址:
https://www.codewars.com/kata/sum-of-pairs/train/python

冬雪雪冬

ooxx7788 发表于 2017-5-11 17:10
还是不行，超时。
这是codewars  5kyu的题目, 这个级别的题目会出现对时间或代码量的限制性要求.
单论 ...

我再想想，看看还有什么办法。

当回首遇上转身

冬雪雪冬 发表于 2017-5-11 16:37
没有更好的想法，用set是否快点。

还有set()这种函数学习了