Find 2 Integers In Array With Given Sum

Question

Given a sorted integer list and an integer, find two integer in the list such that the sum of the two integers equals the given integer. It is required that the time complexity must be O(n). For example, the sorted integer list is {1, 2, 4, 7, 11, 15} and an integer 15. The output is 4 and 11 since 4 + 11 = 15.

Solution

Since the integer list is sorted, it is actually not that difficult. We have to create 2 pointers, 1 at the head and 1 at the tail. Check the sum of them if they equals the given integer. If not, there are 2 conditions: sum is greater or smaller than the integer. if greated, move the tail pointer backward, else move the head pointer forward.

Example

# foundtion to find the integers 
def find_two_suitable_int(integers, wanted_sum): 
    
    # check error 
    if len(integers) <= 1: 
        print "list too short to work on" 
        return (None, None) 
    
    # pointers 
    head = 0 
    tail = len(integers) - 1 
    
    # find the integers 
    while (tail > head): 
        sum = integers[head] + integers[tail] 
        if sum == wanted_sum: 
            return (integers[head], integers[tail]) 
        elif sum > wanted_sum: tail = tail - 1 
        else: head = head + 1 
    
    # no integers are found 
    return (None, None) 

# main testing, output should be 11 and 4 
list = [1, 2, 4, 7, 11, 15] 
(x, y) = find_two_suitable_int(list, 15) 
if x and y: 
    print "the two integers are %s and %s" % (x, y)
else:
    print "can't find suitable integers" 

Extended question

Assuming the list is not sorted, please construct a function that finds the same result with the same O(n).

Solution for extended question

Use hash map to save the value of each item.

Extended Question

# foundtion to find the integers 
def find_two_suitable_int(integers, wanted_sum): 
    
    # generate a map of the integers
    map = {}
    for item in integers:
        map[item] = True
    
    # check the corresponding item
    for item in integers:
        corresponding_item = wanted_sum - item
        if corresponding_item in map:
            return (item, corresponding_item)
    
    # nothing found
    return (None, None)

# main testing, output should be 11 and 4 
list = [1, 4, 7, 15, 11, 2] 
(x, y) = find_two_suitable_int(list, 15) 
if x and y: 
    print "the two integers are %s and %s" % (x, y)
else:
    print "can't find suitable integers"