Python: 每日一题 43

ooxx7788

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

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

1. sum_pairs([11, 3, 7, 5],         10)
   
2. #                 ^-^      3 + 7 = 10
   
3. == [3, 7]
   
4. 
   
5. sum_pairs([4, 3, 2, 3, 4],         6)
   
6. #           ^---^         4 + 2 = 6, index: 0, 2 *
   
7. #             ^---^      3 + 3 = 6, index: 1, 3
   
8. #                 ^---^   2 + 4 = 6, index:  2, 4
   
9. #  * 返回整体最早出现的答案
   
10. == [4, 2]
    
11. 
    
12. sum_pairs([0, 0, -2, 3], 2)
    
13. #  没有可以相加成2的组合.
    
14. == None
    
15. 
    
16. sum_pairs([10, 5, 2, 3, 7, 5],         10)
    
17. #                 ^--------^   5 + 5 = 10, index: 1, 5
    
18. #                    ^-^      3 + 7 = 10, index: 3, 4 *
    
19. #  * 返回整体最早出现的答案
    
20. == [3, 7]

复制代码

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

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

复制代码

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

复制代码

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

余欲渔

1. def sum_pairs(array=[11,3,7,5],interger=10):
   
2.     jg=[]
   
3.     njg=[]
   
4.     l=len(array)
   
5.     x=1
   
6.     for i in range(l-1,0,-1):
   
7.         if i<2:x=0
   
8.         for j in range(i-1,-1,-1):
   
9.             if array[i]+array[j]==interger:
   
10.                 jg=[array[j],array[i],j,i]
    
11.     if x:
    
12.         njg=sum_pairs(array[:jg[3]],interger)
    
13.     if jg==[]:
    
14.         return []
    
15.     elif njg==[]:
    
16.         return str(jg[0])+'+'+str(jg[1])+'='+str(interger)+',index:'+str(jg[2])+','+str(jg[3])
    
17.     else:
    
18.         return str(njg[0])+'+'+str(njg[1])+'='+str(interger)+',index:'+str(njg[2])+','+str(njg[3])
    
19. 
    
20. print(sum_pairs([10,5,2,3,7,5],10))

复制代码

ooxx7788

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

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

冬雪雪冬

没有搞清规则：？

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

复制代码

ooxx7788

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

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

冬雪雪冬

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

明白了。

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

复制代码

ooxx7788

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

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

冬雪雪冬

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

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

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

复制代码

ooxx7788

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

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

复制代码

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

ooxx7788

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

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

冬雪雪冬

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

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

1. def sum_pairs(list1, num):
   
2.     for i in range(1, len(list1)):
   
3.         if num - list1[i] in set(list1[:i]):
   
4.             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)
请问这一句怎么解释啊，求教

冬雪雪冬

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()这种函数学习了