-
Notifications
You must be signed in to change notification settings - Fork 1.1k
Expand file tree
/
Copy paththree_sum.py
More file actions
36 lines (25 loc) · 717 Bytes
/
three_sum.py
File metadata and controls
36 lines (25 loc) · 717 Bytes
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
def threesum(arr, target):
res = []
arr.sort()
length = len(arr)
for i in range(length -2):
if i > 0 and arr[i] == arr[i-1]:
continue
l = i +1
r = length -1
while l < r:
total = arr[i] + arr[l] + arr[r]
if total < target:
l += 1
elif total > target:
r -=1
else:
res.append([arr[i],arr[l],arr[r]])
while l < r and arr[l] == arr[l+1]:
l += 1
while l < r and arr[r] == arr[r-1]:
r -= 1
l +=1
r -=1
return res
print(threesum([-1,0,1,2,-1,-4],0))