-
Notifications
You must be signed in to change notification settings - Fork 0
/
three_sum.py
35 lines (30 loc) · 1.08 KB
/
three_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
from typing import List
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
res = []
if len(nums) < 3:
return res
nums.sort()
for i in range(0, len(nums)-2):
if nums[i] > 0:
return res
if i != 0 and nums[i] == nums[i - 1]:
continue
left, right = i + 1, len(nums) - 1
while left < right:
three_sum = nums[left] + nums[i] + nums[right]
if three_sum == 0:
res.append([nums[left], nums[i], nums[right]])
while left < right and nums[left] == nums[left + 1]:
left += 1
while left < right and nums[right] == nums[right - 1]:
right -= 1
left += 1
right -= 1
elif three_sum > 0:
right -= 1
else:
left += 1
return res
if __name__ == "__main__":
print(Solution().threeSum([-1, 0, 1, 2, -1, -4]))