If the array is sorted in the increasing order, we can scan the array from the two ends of the array to find the matched pair. Therefore, the time complexity is O(n) and the space complexity is O(1).
code:
def find_sum_sort(arr,x):
low = 0
high = len(arr) - 1
found = 0
while low < high:
sum = arr[low]+arr[high] //adding first and last element of the array
if sum == x:
ll = low + 1
while arr[ll] == arr[low]: ll += 1
if arr[low]==arr[high]:
for i in range(low, ll):
for j in range(i+1, ll):
found += 1
print "%d: [%d]=%d - [%d]=%d"%(found, i, arr[i], j, arr[j])
return found
hh = high - 1
while arr[hh] == arr[high]: hh -= 1
for i in range(low, ll):
for j in range(hh+1, high+1):
found += 1
print "%d: [%d]=%d - [%d]=%d"%(found, i, arr[i], j, arr[j])
low = ll
high = hh
elif sum < x:
low += 1
else:
high -= 1
return found
Reference: http://www.cs.uml.edu/~jlu1/doc/codes/findSum.html