Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- # Naive approach - O(n)
- def twoNumberSum(array, targetSum):
- for num in array:
- if num == 0:
- return sorted([num, targetSum])
- if (num < targetSum):
- diff = targetSum - num
- if diff in array:
- if array.index(diff) != array.index(num):
- result = [num, diff]
- return sorted(result)
- return []
- # Better approach - O(nlog(n))
- def twoNumberSum(array, targetSum):
- array.sort()
- left_pointer = 0
- right_pointer = len(array) - 1
- while left < right: # While the pointers don't overlap...
- currentSum = array[left_pointer] + array[right_pointer]
- if currentSum == targetSum:
- return [array[left_pointer], array[right_pointer]]
- # Increase or decrease based on size (list is already sorted)
- elif currentSum < targetSum:
- left_pointer += 1
- elif currentSum > targetSum:
- right_pointer -= 1
- return []
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement