LintCode Q57 3Sum in Python

  • Jinhai ZHOU
  • 5 Minutes
  • 2016年12月18日
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
class Solution:
"""
@param numbersbers : Give an array numbersbers 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
# time complexity: O(n^2log(n))
# space complexity: O(n^2)
# cause python sort is not inplace sort
numbers = sorted(numbers)
lo = 0
hi = len(numbers) - 1
res = set([])
tested = set([])
self.searchTriplet(numbers, lo, hi, res, tested)
return list(res)
def searchTriplet(self, numbers, lo, hi, res, tested):
if lo + 1 >= hi or numbers[lo] > 0 or numbers[hi] < 0 or (lo, hi) in tested:
return
tested.add((lo, hi))
sum = numbers[lo] + numbers[hi]
mid = self.binarySearch(numbers, lo, hi, -sum)
if mid == -1:
pass
else:
res.add((numbers[lo], numbers[mid], numbers[hi]))
self.searchTriplet(numbers, lo + 1, hi, res, tested)
self.searchTriplet(numbers, lo, hi - 1, res, tested)
def binarySearch(self, A, lo, hi, target):
# search between lo ~ hi
# search target in sorted array A
lo, hi = lo + 1, hi - 1
while lo <= hi:
mid = lo + (hi - lo)/2
if A[mid] < target:
lo = mid + 1
elif A[mid] > target:
hi = mid - 1
else:
return mid
return -1
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。