Problem 4: Two Sum (100pts)

Problem

Hugh wants to solve the famous difficult problem: two sum. This problem asks whether there exists two different items in a list whose sum is equal to a given target number. For example, if the list is [1, 2, 3, 4, 5] and the given target number is 7, then the answer is True because 2 + 5 = 7. If the given target number is 2, then the answer is False because no two items sum to 2.

He knows he can solve the problem by enumerating every possible element pairs. He has written a function two_sum_pairs to check if there is a pair in a list of pairs having summation equal to target. Could you please help to write a function pairs that returns the search space of all pairs for input list? You can yield a pair (i, j) with yield i, j, and pattern match a pair with (i, j) = pair.

Hugh 想解决著名的难题：两数之和。这个问题询问在一个列表中是否存在两个不同的项，它们的和等于一个给定的目标数字。例如，如果列表是 [1, 2, 3, 4, 5]，给定的目标数字是 7，那么答案是 True，因为 2 + 5 = 7。如果给定的目标数字是 2，那么答案是 False，因为没有两项的和等于 2。

他知道他可以通过枚举所有可能的元素对来解决这个问题。他已经编写了一个函数 two_sum_pairs 来检查一个对列表中是否存在一个对的和等于 target。您能帮忙编写一个函数 pairs，返回输入列表所有对的搜索空间吗？您可以使用 yield i, j 来产出一个对 (i, j)，并使用 (i, j) = pair 来进行模式匹配。

def two_sum_pairs(target, pairs):
    """Return True if there is a pair in pairs that sum to target."""
    for i, j in pairs:
        if i + j == target:
            return True
    return False

def pairs(lst):
    """Yield the search space for two_sum_pairs.

    >>> two_sum_pairs(1, pairs([1, 3, 3, 4, 4]))
    False
    >>> two_sum_pairs(8, pairs([1, 3, 3, 4, 4]))
    True
    >>> lst = [1, 3, 3, 4, 4]
    >>> plst = pairs(lst)
    >>> n, pn = len(lst), len(list(plst))
    >>> n * (n - 1) / 2 == pn
    True
    """
    "*** YOUR CODE HERE ***"

Suddenly, Hugh got the inspiration that he only needs to visit each element once, because there is a fact that for a given target number target, an element v is a possible candidate for the solution if and only if there exists another element t equals to target - v. Hugh may design a quicker algorithm by utilizing this condition. Could you help him complete the following function? As a reminder, you can check whether an element elem is in a list lst with elem in lst.

突然，Hugh 得到了一个灵感，他只需要访问每个元素一次，因为有一个事实是，对于给定的目标数字 target，一个元素 v 是解的一个可能候选者当且仅当存在另一个元素 t 等于 target - v。Hugh 可以利用这个条件设计一个更快的算法。您能帮他完成以下函数吗？提醒一下，您可以使用 elem in lst 来检查元素 elem 是否在列表 lst 中。

def two_sum_list(target, lst):
    """Return True if there are two different elements in lst that sum to target.

    >>> two_sum_list(1, [1, 3, 3, 4, 4])
    False
    >>> two_sum_list(8, [1, 3, 3, 4, 4])
    True
    """
    visited = []
    for val in lst:
        "*** YOUR CODE HERE ***"

    return False

After you finished, try to register and submit your solution to leetcode too :)

Is Hugh's final solution quicker?

完成后，也尝试在 leetcode 上注册并提交你的解决方案 :)

Hugh 最终的解决方案更快吗？

Hints

Solutions