LintCode Q59 3Sum Closest 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
class Solution:
"""
@param numbers: Give an array numbers of n integer
@param target : An integer
@return : return the sum of the three integers, the sum closest target.
"""
def threeSumClosest(self, numbers, target):
# write your code here
# time complexity: O(n^2)
# space complexity: O(n)
if len(numbers) < 3:
return
numbers = sorted(numbers)
sumClosest = sum(numbers[:3])
hi = len(numbers) - 1
for i in xrange(len(numbers)-2):
lo = i
current_sum = self.searchTuplet(numbers, lo + 1, hi, target - numbers[lo])
if abs(target - sumClosest) > abs(numbers[lo] + current_sum - target):
sumClosest = numbers[lo] + current_sum
return sumClosest
def searchTuplet(self, numbers, lo, hi, target):
# find tuplet that has cloest sum to target
sumClosest = numbers[lo] + numbers[hi]
while lo < hi:
if numbers[lo] + numbers[hi] < target:
if abs(target - sumClosest) > abs(numbers[lo] + numbers[hi] - target):
sumClosest = numbers[lo] + numbers[hi]
lo += 1
elif numbers[lo] + numbers[hi] > target:
if abs(target - sumClosest) > abs(numbers[lo] + numbers[hi] - target):
sumClosest = numbers[lo] + numbers[hi]
hi -= 1
else: # numbers[lo] + numbers[hi] == target
return target
return sumClosest
知识共享许可协议
本作品采用知识共享署名-相同方式共享 4.0 国际许可协议进行许可。