SHARE
TWEET

Untitled

a guest Sep 16th, 2019 87 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. # Naive approach - O(n)
  2. def twoNumberSum(array, targetSum):
  3.     for num in array:
  4.         if num == 0:
  5.             return sorted([num, targetSum])
  6.         if (num < targetSum):
  7.             diff = targetSum - num
  8.             if diff in array:
  9.                 if array.index(diff) != array.index(num):
  10.                     result = [num, diff]
  11.                     return sorted(result)
  12.                    
  13.     return []
  14.  
  15. # Better approach - O(nlog(n))
  16. def twoNumberSum(array, targetSum):
  17.     array.sort()
  18.     left_pointer = 0
  19.     right_pointer = len(array) - 1
  20.     while left < right: # While the pointers don't overlap...
  21.         currentSum = array[left_pointer] + array[right_pointer]
  22.     if currentSum == targetSum:
  23.         return [array[left_pointer], array[right_pointer]]
  24.     # Increase or decrease based on size (list is already sorted)
  25.     elif currentSum < targetSum:
  26.         left_pointer += 1
  27.     elif currentSum > targetSum:
  28.         right_pointer -= 1
  29.     return []
RAW Paste Data
We use cookies for various purposes including analytics. By continuing to use Pastebin, you agree to our use of cookies as described in the Cookies Policy. OK, I Understand
Not a member of Pastebin yet?
Sign Up, it unlocks many cool features!
 
Top