给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 *a，b，c ，*使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

注意：答案中不可以包含重复的三元组。

例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]， 满足要求的三元组集合为： [ [-1, 0, 1], [-1, -1, 2] ] 

解题思路

我们首先想到的解法是通过三重循环，于是我就写出了如下代码：

讯享网class Solution: def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ result = [] for i, a in enumerate(nums): for j, b in enumerate(nums[i + 1:]): for _, c in enumerate(nums[j + i + 2:]): if a + b + c == 0: result.append([a, b, c]) return result 

但是上面这个代码是有问题的，因为我们没有考虑结果重复的问题。接着我们想到可以通过collections.Counter记录所有数字出现的次数，如果前后有相同的话，我们就不添加到result中去。于是就有了下面的写法

class Solution: def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ from collections import Counter k = [] result = [] for i, a in enumerate(nums): for j, b in enumerate(nums[i + 1:]): for _, c in enumerate(nums[j + i + 2:]): if a + b + c == 0 and Counter([a, b, c]) not in k: k.append(Counter([a, b, c])) for i in k: result.append(list(i.elements())) return result 

但是这种写法的缺点很明显，算法的时间复杂度是O(n^3)这个级别的。我们能不能优化到O(n^2)这个级别呢？我们可以参考Leetcode 1:两数之和（最详细解决方案！！！）文中的方法，通过一个hash表来记录nums中所有元素出现的次数。

讯享网class Solution: def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ nums_hash = { 
   } result = list() for num in nums: nums_hash[num] = nums_hash.get(num, 0) + 1 if 0 in nums_hash and nums_hash[0] >= 3: result.append([0, 0, 0]) nums = sorted(list(nums_hash.keys())) # trick for i, num in enumerate(nums): for j in nums[i+1:]: if num*2 + j == 0 and nums_hash[num] >= 2: result.append([num, num, j]) if j*2 + num == 0 and nums_hash[j] >= 2: result.append([j, j, num]) dif = 0 - num - j if dif > j and dif in nums_hash: # trick result.append([num, j, dif]) return result 

注意上面写法中的trick，我们通过对nums_key的排序，这样我们就可以确定存入结果中的list中元素的顺序，这样就可以避免重复存入相同的元素。（大多数避免重复的问题，思路都是排序）

当然这个算法还有优化的空间，我们知道三个数和为0，那么在三个数不全为0的情况下，必然有一个正数和一个负数，那么我们可以通过两个list去存取nums中含有不重复元素的正数和负数。那样我们就不用O(n^2)（n=len(nums)）的时间，而只需要O(n*m)（n+m=len(nums)）的时间复杂度。

另外我们还知道一个条件，对于a,b,c三个数，如果a是正数，b是负数，此时存在两种情况：1）有两个数相同。2）所有数都不同。

讯享网

例如：

a = 1 b = -2 c = 1 ------------- a = 3 b = -2 c = -1 

对于第一种情况，当我们枚举a和b的时候，只需要判断c是不是a或b中的一个即可。对于第二种情况，此时c可能是正数也可能是负数，为了避免重复选取，我们选择满足c < b（如果c是负数）或者c > a（如果c是正数）的那组数。例如上面的第二个例子就不会选取，而如果a=3,b=-1,c=-2就会选取。

讯享网class Solution: def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ nums_hash = { 
   } result = list() for num in nums: nums_hash[num] = nums_hash.get(num, 0) + 1 if 0 in nums_hash and nums_hash[0] >= 3: result.append([0, 0, 0]) neg = list(filter(lambda x: x < 0, nums_hash)) pos = list(filter(lambda x: x>= 0, nums_hash)) for i in neg: for j in pos: dif = 0 - i - j if dif in nums_hash: if dif in (i, j) and nums_hash[dif] >= 2: result.append([i, j, dif]) if dif < i or dif > j: result.append([i, j, dif]) return result 

此处应有掌声，非常好的解法是不是O(∩_∩)O

另外这个问题我们也可以使用Leetcode 167:两数之和 II - 输入有序数组（最详细解决方案！！！）这篇文章中提到的对撞指针的思路。我们首先要将nums排序。

-4 -1 -1 0 1 2 i l r l = i+1 

我们先要对nums排序，然后我们只要考虑nums[i] <= 0的部分，因为当nums[i] > 0时，必然会造成nums[i], nums[l], nums[r]全部>0，这显然不对。当i > 0时，我们要考虑nums[i - 1] == nums[i]，如果成立，我们要跳出本次循环，执行++i，直到不成立为止。

所以我们就有了如下的做法

讯享网class Solution: def threeSum(self, nums): """ :type nums: List[int] :rtype: List[List[int]] """ result = list() nums_len = len(nums) if nums_len < 3: return result l, r, dif = 0, 0, 0 nums.sort() for i in range(nums_len - 2): if nums[i] > 0: break if i > 0 and nums[i - 1] == nums[i]: continue l = i + 1 r = nums_len - 1 dif = -nums[i] while l < r: if nums[l] + nums[r] == dif: result.append([nums[l], nums[r], nums[i]]) while l < r and nums[l] == nums[l + 1]: l += 1 while l < r and nums[r] == nums[r - 1]: r -= 1 l += 1 r -= 1 elif nums[l] + nums[r] < dif: l += 1 else: r -= 1 return result 

我将该问题的其他语言版本添加到了我的GitHub Leetcode

如有问题，希望大家指出！！！