-
Notifications
You must be signed in to change notification settings - Fork 228
/
three-number-sum.py
51 lines (43 loc) · 1.02 KB
/
three-number-sum.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# THREE NUMBER SUM
# USING HASH TABLES AND EXTRA SPACE
def threeNumberSum(array, targetSum):
# Write your code here.
array.sort()
result = []
for i,x in enumerate(array):
target = targetSum - x
possibleTwoSums = twoNumberSum(array[i+1:], target)
for y in possibleTwoSums:
y.insert(0, x)
result.append(y)
return result
def twoNumberSum(array, target):
store = {}
twoSums = []
for x in array:
value = target - x
if value in store:
twoSums.insert(0, [value, x])
store[x] = True
return twoSums
# USING POINTERS. O(N) space and O(N^2) time
def threeNumberSum(array, targetSum):
# Write your code here.
result = []
array.sort()
i = 0
while i < len(array) - 2:
left = i + 1
right = len(array) - 1
while left < right:
currentSum = array[i] + array[left] + array[right]
if currentSum == targetSum:
result.append([array[i], array[left], array[right]])
left += 1
right -= 1
elif currentSum < targetSum:
left += 1
else:
right -= 1
i += 1
return result