-
Notifications
You must be signed in to change notification settings - Fork 0
/
3sum.py
32 lines (31 loc) · 1.03 KB
/
3sum.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
'''
给出一个有n个整数的数组S,在S中找到三个整数a, b, c,找到所有使得a + b + c = 0的三元组。
'''
class Solution:
"""
@param: numbers: Give an array numbers of n integer
@return: Find all unique triplets in the array which gives the sum of zero.
"""
def threeSum(self, numbers):
# write your code here
res = []
l = len(numbers)
if l < 3:
return res
numbers.sort()
for i in xrange(l):
target = 0 - numbers[i]
# 2 sum
left, right = i + 1, l - 1
while left < right:
if numbers[left] + numbers[right] == target:
r = [numbers[i], numbers[left], numbers[right]]
if r not in res:
res.append(r)
left += 1
right -= 1
elif numbers[left] + numbers[right] < target:
left += 1
else:
right -= 1
return res