16.最接近的三数之和
题解排序+双指针算法流程：复杂度分析PythonJava(待完成)
题解
排序+双指针
算法流程：
特判，对于数组长度
n
n
n，如果数组为Null或者数组长度小于3，返回
[
]
[]
[]。对数组进行排序，并定义
r
e
s
=
m
a
x
n
u
m
res=maxnum
res=maxnum，保存最接近和。遍历排序后数组：
对于重复元素，跳过，避免重复计算（也可以不跳过）令左指针
L
=
i
+
1
L=i+1
L=i+1,右指针
R
=
n
−
1
R=n-1
R=n−1,当
L
<
R
L<R
L<R时，执行循环： *令
c
u
r
_
s
u
m
=
n
u
m
s
[
i
]
+
n
u
m
s
[
L
]
+
n
u
m
s
[
R
]
cur\_sum=nums[i]+nums[L]+nums[R]
cur_sum=nums[i]+nums[L]+nums[R],如果
c
u
r
_
s
u
m
=
t
a
r
g
e
t
cur\_sum=target
cur_sum=target,返回
t
a
r
g
e
t
target
target *若
a
b
s
(
c
u
r
_
s
u
m
−
t
a
r
g
e
t
)
<
a
b
s
(
r
e
s
−
t
a
r
g
e
t
)
abs(cur\_sum-target)<abs(res-target)
abs(cur_sum−target)<abs(res−target),说明
c
u
r
_
s
u
m
cur\_sum
cur_sum更接近目标，更新
r
e
s
res
res *若
c
u
r
_
s
u
m
−
t
a
r
g
e
t
cur\_sum-target
cur_sum−target大于0，说明
n
u
m
s
[
R
]
nums[R]
nums[R]太大，
R
R
R左移 *若
c
u
r
_
s
u
m
−
t
a
r
g
e
t
cur\_sum-target
cur_sum−target小于0，说明
n
u
m
s
[
L
]
nums[L]
nums[L]太小，
L
L
L右移
复杂度分析
时间复杂度：
O
(
n
2
)
O\left(n^{2}\right)
O(n2)，数组排序
O
(
N
log
N
)
O(N \log N)
O(NlogN)，遍历数组
O
(
n
)
O\left(n\right)
O(n)，双指针遍历
O
(
n
)
O\left(n\right)
O(n)，总体
O
(
N
log
N
)
+
O
(
n
)
∗
O
(
n
)
O(N \log N)+O\left(n\right)*O\left(n\right)
O(NlogN)+O(n)∗O(n)，
O
(
n
2
)
O\left(n^{2}\right)
O(n2)空间复杂度：
O
(
1
)
O(1)
O(1)
Python
class Solution:
def threeSumClosest(self
, nums
: List
[int], target
: int) -> int:
n
=len(nums
)
if(not nums
or n
<3):
return None
nums
.sort
()
res
=float("inf")
for i
in range(n
):
if(i
>0 and nums
[i
]==nums
[i
-1]):
continue
L
=i
+1
R
=n
-1
while(L
<R
):
cur_sum
=nums
[i
]+nums
[L
]+nums
[R
]
if(cur_sum
==target
):
return target
if(abs(cur_sum
-target
)<abs(res
-target
)):
res
=cur_sum
if(cur_sum
-target
<0):
L
+=1
else:
R
-=1
return res
Java(待完成)
