排序 + 双指针
本题的难点在于如何去除重复解
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
| class Solution:
def threeSum(self,nums):
nums.sort()
a=[]
for k in range(len(nums)-2):
if nums[k]==nums[k-1] and k>0:
continue
i=k+1
j=len(nums)-1
while i<j:
left=nums[i]
right=nums[j]
total=nums[k]+left+right
if total==0:
a.append([nums[k],nums[i],nums[j]])
while i<j and nums[i]==nums[i+1]:
i+=1
while i<j and nums[j]==nums[j-1]:
j-=1
i+=1
j-=1
elif total<0:
i+=1
else:
j-=1
return a
|
特判，对于数组长度 n，如果数组为 null 或者数组长度小于 3，返回 []。
对数组进行排序。
遍历排序后数组：
若 nums[i]>0：因为已经排序好，所以后面不可能有三个数加和等于 0，直接返回结果。
对于重复元素：跳过，避免出现重复解
令左指针 L=i+1，右指针 R=n−1，当 L<R 时，执行循环：
当 nums[i]+nums[L]+nums[R]== 0
执行循环，判断左界和右界是否和下一位置重复，去除重复解。
(这一步最细，因为同一个num[i]可以配不同的num[L],num[R],即使一开始有total=0，后续也可以有一对，所以这里还有去重和检查一遍)
并同时将 L,R 移到下一位置，寻找新的解
若和大于 0，说明 nums[R] 太大，R 左移
若和小于 0，说明 nums[L] 太小，L 右移
