Suppose we have two sorted lists, and we want to find one element from the first, and the other element from the 2nd list, where the sum of the two elements equal to a given target. If there are multiple combinations, need to find all the combinations.
Any bugs, performance improvement ideas in terms of algorithm time complexity or code style advice is highly appreciated. My basic idea is to scan the first list from the beginning, and scan the second list from the end, a similar approach to how we resolve the 2-sum classic problem in one list.
def two_sum(list1, list2, target, result):
i = 0
j = len(list2) - 1
while i < len(list1) and j >= 0:
if list1[i] + list2[j] == target:
result.append((list1[i], list2[j]))
i += 1
j -= 1
while i < len(list1) and list1[i] == list1[i-1]:
i += 1
while j >= 0 and list2[j] == list2[j+1]:
j -= 1
elif list1[i] + list2[j] > target:
j -= 1
else:
i += 1
if __name__ == "__main__":
list1 = [1,3,5,7]
list2 = [2,3,4,5]
result = []
two_sum(list1, list2, 6, result)
print result