解题思路：常规解法很容易想到O(n^3)的解法，但是，n最大为1000，很显然会超时。
如何优化到O(n^2)，a+b+c =0，我们只需要判断 a+b的相反数是否在数组中出现，而且元素的取值范围在1e5的范围内，所以，我们可以空间换时间，开辟一个数组，将第三层的查询O(n)的复杂度降到O(1)，需要注意的是，要考虑去重的情况。
更好的解法：因为常规解法空间消耗有点大，如何降低空间复杂度。
可以使用双指针，也需要先对nums数组从小到大排好序，在第一层循环中，从0开始遍历，枚举可能的a，然后把a后的区间使用 l ,r 双指针枚举，如果 a + l +r >0，说明 r 应该往左移；a + l+r < 0 ，说明 l 应该往右移；a + l + r =0 ，添加答案，l 往右移并且 r 往左移。
此外，需要考虑重复的情况，分别设立 pre_a、pre_l、pre_r三个变量记录上一个值是多少，这样再判断 a + l + r =0 时，
还需判断 ! (pre_l == l and pre_r == r ) 为真才能添加，最外层 如果 a==pre_a，跳过a这个元素。
#常规解法 class Solution: def threeSum(self, nums): mp = [0]*4*100500 a = [] for num in nums: if mp[num]==0: a.append(num) if mp[num]<2: mp[num]+=1 elif mp[num] == 2 and num==0: mp[num]+=1 ans = [] a = sorted(a) idx = {} for x in range(len(a)): idx[a[x]]=x if mp[0]==3: ans.append([0,0,0]) for i in range(len(a)): if mp[a[i]]==2 and a[i]!=0: if mp[-2*a[i]]: ans.append([a[i],a[i],-2*a[i]]) for j in range(i+1,len(a)): tmp = a[i]+a[j] if mp[-tmp] and idx[a[i]]<idx[a[j]]<idx[-tmp]: ans.append([a[i],a[j],-tmp]) return ans # #双指针解法 # class Solution: def threeSum(self, nums): a = sorted(nums) ans =[] inf = int(1e9) pre_i = -inf #print(a) for i in range(len(a)): if pre_i==a[i]: continue l = i+1 r = len(a)-1 pre_l = - inf pre_r = inf while l<r: if a[i]+a[l]+a[r]==0: if not(a[l]==pre_l and a[r]==pre_r): ans.append([a[i],a[l],a[r]]) pre_l = a[l] pre_r = a[r] l+=1 r-=1 elif a[i]+a[l]+a[r]<0: pre_l = a[l] l+=1 else: pre_r = a[r] r-=1 pre_i = a[i] return ans
原文：https://www.cnblogs.com/ISGuXing/p/14607699.html
