interview-arithmetic/JRTT-find-num-1/find-num-1.py

#!/usr/bin/env python
# -*- coding:utf-8 -*-

"""
Q:
给函数传递一个正整数的列表alist和一个正整数T，假装它等于[1,3,6,4,2,7]，给出alist里所有相加等于T的元素的list，
每个数只用一次。比如T=7，列表里3+4=7，7=7，1+6=7。你的函数就要返回[[3,4],[7],[1,6]]

A:
1. 如果列表里面每个数字不可以重复，解法利用哈希标记，这是k-num算法在面对2元数据时的思想
2. 如果列表里面每个数字可以重复，就在find_num里dict的标记，把True和False改为剩余没有用过的个数

"""

def find_num(alist, T):
    mark = {}
    for v in alist:
        mark[v] = True

    result = []
    for v in alist:
        if not mark[v]:
            continue
        if v == T:
            result.append([v])
            mark[v] = False
            continue

        if mark.__contains__(T-v) and mark[T - v]:
            result.append([v, T - v])
            mark[v] = False
            mark[T - v] = False

    return result


if __name__ == '__main__':
    n = 0
    T = 0
    while True:
        print("input T:")
        T = int(input())
        print('input data length:')
        n = int(input())
        print('input digits: ')
        alist = []
        for i in range(0, n):
            digit = int(input())
            alist.append(digit)

        result = find_num(alist, T)
        print(result)