源码: example1
# -.- coding:utf-8 -.-
# 给定一个数字, 在一个任意序列的列表中找到两个为一组的
# 数字(一组或多组)相加结果等于给定数字, 返回一组或多组.
#
# 例如:
# 列表: [1, 2, 3, 4, 5, 6, 7, 8, 9,]
# 给定一个数字: 15
# 应得出结果: (6, 9), (7, 8)
def target_sum(array, number):
sorted_array = sorted(array)
result = []
for i in sorted_array:
for j in sorted_array:
print("s")
if i + j == number:
result.append((i, j))
return result
def main():
print(target_sum([1, 2, 3, 4, 5, 6, 7, 8, 9], 15))
if __name__ == '__main__':
main()
# output:
# [(6, 9), (7, 8), (8, 7), (9, 6)]
# TODO: 结果没问题, 但是在唯一约束列表中出现冗余结果, 不是特别合适
# TODO: 而且这种写法是以二次幂的基数增长, 当列表越大时越慢!
源码: example2
# -.- coding:utf-8 -.-
# 给定一个数字, 在一个任意序列的列表中找到两个为一组的
# 数字(一组或多组)相加结果等于给定数字, 返回一组或多组.
#
# 例如:
# 列表: [1, 2, 3, 4, 5, 6, 7, 8, 9,]
# 给定一个数字: 15
# 应得出结果: (6, 9), (7, 8)
def target_sum(array, number):
sorted_array = sorted(array)
minimal = 0
maximum = len(sorted_array) - 1
result = []
if maximum <= 0:
return result
while minimal <= maximum:
mi = sorted_array[minimal]
ma = sorted_array[maximum]
# 这种写法: 列表有多少个元素, 最多也就匹配多少次, 效率会高很多.
if mi + ma > number:
maximum -= 1
elif mi + ma < number:
minimal += 1
else:
result.append((mi, ma))
minimal += 1
maximum -= 1
return result
def main():
print(target_sum([1, 2, 3, 4, 5, 6, 7, 8, 9], 15))
if __name__ == '__main__':
main()
# output:
# [(6, 9), (7, 8)]
