Problem 4: Two Sum (100pts)

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.

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.

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?