-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathleetcode_16.py
More file actions
33 lines (30 loc) · 810 Bytes
/
leetcode_16.py
File metadata and controls
33 lines (30 loc) · 810 Bytes
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
# coding=utf-8
from typing import List
import sys
class Solution:
"""
求和最接近目标值的三个数
"""
def three_sum_closest(self, nums: List[int], target: int) -> int:
"""
Time: O(n^2), Space: O(1)
:param nums:
:return:
"""
res = -sys.maxsize
k = len(nums) - 1
nums.sort()
while k >= 2:
left, right = 0, k - 1
while left < right:
s = nums[left] + nums[right] + nums[k]
if s == target:
return target
if s < target:
left += 1
else:
right -= 1
if abs(target - s) < abs(target - res):
res = s
k -= 1
return res