先sort list，枚举第一个数i=1~n-2，然后设置两个游标，左边从i+1向右，右边从n向左，如果两个游标对应的数之和小于-nums[i]，第一个游标右移，否则第二个右边左移，如果正好等于-nums[i]，看是否与前一个set重复，不重复则加入答案
一开始尝试记录所有答案，最后去重，会TLE，边处理边判重需要注意方式，当答案集合为空或者不是（第一个数与上一个答案一样第二个数却小于等于上一个答案）时，加入答案集合
if tp == [] or not (nums[i] == tp[-1][0] and nums[pos1] <= tp[-1][1]):
"
可以用以下case做测试（自己之前的Output不能通过这个case，WA了一次）：
"
Input:
[-4,-2,-2,-2,0,1,2,2,2,3,3,4,4,6,6]
Output:
[[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2],[-2,-2,4],[-2,0,2]]
Expected:
[[-4,-2,6],[-4,0,4],[-4,1,3],[-4,2,2],[-2,-2,4],[-2,0,2]]
"
Runtime: 6730 ms, faster than 9.07% of Python online submissions for 3Sum.
Memory Usage: 16.7 MB, less than 79.63% of Python online submissions for 3Sum.
1 #15
2 #Runtime: 6730 ms
3 #Memory Usage: 16.7 MB
4
5 class Solution(object):
6 def threeSum(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[List[int]]
10 """
11 nums.sort()
12 d = {}
13 for i in range(len(nums)):
14 d[nums[i]] = i
15 tp = []
16 ans = []
17 for i in range(len(nums)):
18 pos1 = i + 1
19 pos2 = len(nums) - 1
20 while pos1 < pos2:
21 if nums[pos1] + nums[pos2] == -nums[i]:
22 if tp == [] or not (nums[i] == tp[-1][0] and nums[pos1] <= tp[-1][1]):
23 tp.append([nums[i], nums[pos1], nums[pos2]])
24 pos1 += 1
25 pos2 -= 1
26 elif nums[pos1] + nums[pos2] > -nums[i]:
27 pos2 -= 1
28 else:
29 pos1 += 1
30 return tp
思路二（比思路一快一点）：
先sort，再用dict记录这一列数里面每一种值最后出现的下标位置
两重for循环枚举前两个数i，j，看第三个数在不在dict里，如果在的话，要求下标k>j>i，与思路一一样，注意判断是否与现有的数重复，如果全部加入结果集合最后再判重会TLE
Runtime: 3584 ms, faster than 21.33% of Python online submissions for 3Sum.
Memory Usage: 17.2 MB, less than 19.67% of Python online submissions for 3Sum.
1 #15
2 #Runtime: 3584 ms
3 #Memory Usage: 17.2 MB
4
5 class Solution(object):
6 def threeSum(self, nums):
7 """
8 :type nums: List[int]
9 :rtype: List[List[int]]
10 """
11 nums.sort()
12 d = {}
13 for i in range(len(nums)):
14 d[nums[i]] = i
15 tp = []
16 ans = []
17 for i in range(len(nums)):
18 for j in range(i + 1, len(nums)):
19 if -(nums[i] + nums[j]) in d:
20 k = d[-(nums[i] + nums[j])]
21 if k > j and (tp == [] or not (nums[i] == tp[-1][0] and nums[j] <= tp[-1][1])):
22 tp.append([nums[i], nums[j], nums[k]])
23 return tp