-
Notifications
You must be signed in to change notification settings - Fork 0
/
16.最接近的三数之和.py
53 lines (46 loc) · 1.84 KB
/
16.最接近的三数之和.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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution(object):
def threeSumClosest(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# 核心思想
# 排序+双指针
# 先对列表排序,然后采用双指针方法
# 每次先固定一个值nums[i],
# 设定数值小的指针为nums[i+1],数值大的指针为nums[len(nums) - 1 ]
# 每次计算sum = nums[i] + nums[i+1] + nums[len(nums) - 1 ]
# 设diffnum用来记录与sum与target差的绝对值,设ans记录此次的sum
# 若计算的出比上一次的小,则更新diffsum 和 ans
# diffnum为int类型的最大值
n = len(nums)
nums.sort()
import sys
diffnum = sys.maxsize # 设定diffnum为int类型的最大值
ans = 0
for i in range(n-2):
k, j = i + 1, len(nums) - 1 # 设定双指针
while k < j:
# 若小的指针移动至大指针右侧则结束循环
sum = nums[i] + nums[k] + nums[j]
tmp = abs(sum - target)
if tmp < diffnum:
# 若此处差值比上次小,则跟新diffnum 和 sum
diffnum = tmp
ans = sum
if sum == target:
# 若sum 正好等于target返回target
return target
elif sum < target:
# 若sum小于target,则移动数值小的指针向右,增大sum
k += 1
else:
# 若sum大于target,则移动数值大的指针向左,减小sum
j -= 1
return ans
nums = [-1,2,1,-4]
x = 1
s = Solution()
a = s.threeSumClosest(nums, x)
print(a)