forked from shuboc/LeetCode-2
-
Notifications
You must be signed in to change notification settings - Fork 0
/
3sum-closest.py
38 lines (35 loc) · 1.21 KB
/
3sum-closest.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
36
37
38
# Time: O(n^2)
# Space: O(1)
# Given an array S of n integers,
# find three integers in S such that the sum is closest to a given number,
# target.
# Return the sum of the three integers.
# You may assume that each input would have exactly one solution.
#
# For example, given array S = {-1 2 1 -4}, and target = 1.
#
# The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
nums, result, min_diff, i = sorted(nums), float("inf"), float("inf"), 0
while i < len(nums) - 2:
if i == 0 or nums[i] != nums[i - 1]:
j, k = i + 1, len(nums) - 1
while j < k:
diff = nums[i] + nums[j] + nums[k] - target
if abs(diff) < min_diff:
min_diff = abs(diff)
result = nums[i] + nums[j] + nums[k]
if diff < 0:
j += 1
elif diff > 0:
k -= 1
else:
return target
i += 1
return result