找出列表中任意两个数字相加等于给定值

源码: 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)]