Given an integer array and a number T, find all *unique* pairs of (a, b) whose sum is equal to T

find_pairs.py

#!/usr/bin/env python

# Given an integer array and a number T, find all *unique* pairs of (a, b) whose sum is equal to T


# O(n), however is not ordered
def find_pairs(arr, target):
    # https://www.ics.uci.edu/~pattis/ICS-33/lectures/complexitypython.txt

    # Convert to hash, O(n)
    arry = set(arr)
    output = set()

    for num in arr:
        n = target - num

        # O(1) look up for hash
        if n in arry and (num, n) not in output:
            # O(1) to add
            output.add((num, n))

    return output

if __name__ == '__main__':

    print list(find_pairs([1, 4, 8, 3, 2, 8, 4, 5], 8))
    #[(5, 3), (4, 4), (3, 5)]