# 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"
```