15.三数之和 Three Sum
题解排序+双指针算法流程：复杂度分析PythonJava(待完成)
题解
排序+双指针
本题的难点在于如何去除重复解
算法流程：
特判，对于数组长度
n
n
n，如果数组为Null或者数组长度小于3，返回
[
]
[]
[]。对数组进行排序。遍历排序后数组：
若
n
u
m
s
[
i
]
>
0
nums[i]>0
nums[i]>0，因为已经排序好，所以后面不可能有三个数加和等于0，直接返回结果。对于重复元素，跳过，避免出现重复解令左指针
L
=
i
+
1
L=i+1
L=i+1,右指针
R
=
n
−
1
R=n-1
R=n−1,当
L
<
R
L<R
L<R时，执行循环： *当
n
u
m
s
[
i
]
+
n
u
m
s
[
L
]
+
n
u
m
s
[
R
]
=
=
0
nums[i]+nums[L]+nums[R]==0
nums[i]+nums[L]+nums[R]==0,执行循环，判断左界和右界是否和下一位置重复，去除重复解。并同时将
L
,
R
L,R
L,R移到下一位置，寻找新的解 *若和大于0，说明
n
u
m
s
[
R
]
nums[R]
nums[R]太大，
R
R
R左移 *若和小于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 threeSum(self
, nums
: List
[int]) -> List
[List
[int]]:
n
=len(nums
)
res
=[]
if(not nums
or n
<3):
return []
nums
.sort
()
res
=[]
for i
in range(n
):
if(nums
[i
]>0):
return res
if(i
>0 and nums
[i
]==nums
[i
-1]):
continue
L
=i
+1
R
=n
-1
while(L
<R
):
if(nums
[i
]+nums
[L
]+nums
[R
]==0):
res
.append
([nums
[i
],nums
[L
],nums
[R
]])
while(L
<R
and nums
[L
]==nums
[L
+1]):
L
=L
+1
while(L
<R
and nums
[R
]==nums
[R
-1]):
R
=R
-1
L
=L
+1
R
=R
-1
elif(nums
[i
]+nums
[L
]+nums
[R
]>0):
R
=R
-1
else:
L
=L
+1
return res
Java(待完成)
