Skip to content

Instantly share code, notes, and snippets.

@kirillsulim
Last active March 23, 2018 18:51
Show Gist options
  • Save kirillsulim/3dcffd215a58590276cb07f082fe7065 to your computer and use it in GitHub Desktop.
Save kirillsulim/3dcffd215a58590276cb07f082fe7065 to your computer and use it in GitHub Desktop.
Algorithm find two numbers sum equals given x
def find_pairs(array, x):
result = []
array = sorted(set(array))
first = 0
last = len(array) - 1
while True:
first_el = array[first]
last_el = array[last]
if x == first_el + last_el:
result.append((first_el, last_el))
last = last - 1
elif x > first_el + last_el:
first = first + 1
elif x < first_el + last_el:
last = last - 1
if first == last:
break
return result
def find_pairs_hash(array, x):
result = []
hash = {}
for i in range(0, len(array)):
hash[array[i]] = i
for i in range(0, len(array)):
el = array[i]
if (x - el) in hash and hash[x - el] != hash[el]:
result.append((x - el, el))
return result
#$ 1-12 5-8
a = [1,2,3,5,7,8,9,12,15]
print("simple")
for x in find_pairs(a, 13):
print(x)
print("hash")
for x in find_pairs_hash(a, 13):
print(x)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment