先sort list，枚舉第一個(gè)數(shù)i=1~n-2，然后設(shè)置兩個(gè)游標(biāo)，左邊從i+1向右，右邊從n向左，如果兩個(gè)游標(biāo)對應(yīng)的數(shù)之和小于-nums[i]，第一個(gè)游標(biāo)右移，否則第二個(gè)右邊左移，如果正好等于-nums[i]，看是否與前一個(gè)set重復(fù)，不重復(fù)則加入答案
一開始嘗試記錄所有答案，最后去重，會TLE，邊處理邊判重需要注意方式，當(dāng)答案集合為空或者不是（第一個(gè)數(shù)與上一個(gè)答案一樣第二個(gè)數(shù)卻小于等于上一個(gè)答案）時(shí)，加入答案集合
if tp == [] or not (nums[i] == tp[-1][0] and nums[pos1] <= tp[-1][1]):
"
可以用以下case做測試（自己之前的Output不能通過這個(gè)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
思路二（比思路一快一點(diǎn)）：
先sort，再用dict記錄這一列數(shù)里面每一種值最后出現(xiàn)的下標(biāo)位置
兩重for循環(huán)枚舉前兩個(gè)數(shù)i，j，看第三個(gè)數(shù)在不在dict里，如果在的話，要求下標(biāo)k>j>i，與思路一一樣，注意判斷是否與現(xiàn)有的數(shù)重復(fù)，如果全部加入結(jié)果集合最后再判重會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