欢迎收藏Star我的Machine Learning Blog:https://github.com/purepisces/Wenqing-Machine_Learning_Blog。如果收藏star, 有问题可以随时与我交流, 谢谢大家！
链接:
直觉
示例:
输入: nums = [-1, 0, 1, 2, -1, -4]
输出: [[-1, -1, 2], [-1, 0, 1]]
解释:
nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0。
nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0。
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0。
不同的三元组是 [-1, 0, 1] 和 [-1, -1, 2]。
注意输出的顺序和三元组的顺序无关。
首先，我们应该记住，解决方案集不得包含重复的三元组。考虑这个示例 [-3, 3, 4, -3, 1, 2]，我们需要找到 _+_+_ = 0。如果我们先看索引 0，那么它将填充 -3(索引[0]) + 1 + 2 = 0。但是，当我们到达索引 3 时，它仍然具有相同的组合，即 -3(索引[3]) + 1 + 2 = 0。这就是重复的。因此，我们可以首先对数组进行排序来处理它。在这种情况下，它将排序为 [-3, -3, 1, 2, 3, 4]，当我们遇到第二个 -3 时，我们可以跳过它。
对于 _+_+_ = 0，当我们选择第一个元素时，我们需要在剩余排序数组中找到两个元素，它们的和等于负的第一个元素值。然后它转换为一个两数之和的问题，类似于问题 167-两数之和 II-输入数组已排序，即在排序数组中找到两个数的和。在此示例中，排序后的数组将变为 [-4, -1, -1, 0, 1, 2]，我们应该遍历整个数组，找到 -4 + [-1, -1, 0, 1, 2] = 0，然后 -1 + [-1, 0, 1, 2] = 0，然后跳过第二个 -1，然后 0 + [1, 2] = 0，等等。
当我们遍历整个数组时，我们还应该添加一些基本情况。如果 nums[i] > 0，那么我们中断，因为数组是递增顺序的。如果 nums[i] == nums[i-1]，我们应该继续循环，因为如果我们不进行此操作，答案将重复。考虑 [-1, -1, 0, 1, 2]。对于第一个 -1，它将有 [-1, -1, 2] 和 [-1, 0, 1]。对于第二个 -1，它也将有 [-1, 0, 1]，这会重复答案。因为第一个 -1 的剩余数组包含了第二个 -1 的剩余数组。
然后我们可以处理这个问题。让两个指针指向剩余数组的开始和结束位置：左指针为 i + 1，右指针为数组的末尾位置。如果这三个值小于 0，那么将 l 向右移动。如果这三个值大于 0，那么将 r 向左移动。否则，我们可以将这三个值追加到结果中。之后，我们应该增加左指针并减少右指针，因为数组不仅包含一个解决方案。然而，为了避免重复的解决方案，我们还需要做一个额外的步骤。考虑 -1[0, 0, 0, 1, 1]。如果 left+1，我们移动到第二个 0 和第一个 1。那么，因为第二个 0 与第一个 0 是相同的值，我们不能将其视为额外的解决方案。我们应该继续将左指针向右移动且不超过右指针。最后，左指针将位于第一个 1，与右指针在同一位置，它将不会进入 while l < r 循环，结果不会追加它。
方法
- 对数组进行排序。
- 遍历排序后的数组，对于每个索引，将剩余元素转换为两数之和问题。
- 通过在处理两数之和问题时检查
nums[l] == nums[l-1]，以及在选择基值时检查nums[i] == nums[i-1]来避免重复的解决方案。 - 最后，返回结果。
复杂度
- 时间复杂度:
O ( n 2 ) O(n^2) O(n2)- 对数组进行排序需要 O ( n log n ) O(n \log n) O(nlogn)，并且在循环中使用双指针方法需要 O ( n 2 ) O(n^2) O(n2)，
复杂度
-
时间复杂度:
O ( n 2 ) O(n^2) O(n2)- 对数组进行排序需要 O ( n log n ) O(n \log n) O(nlogn)，并且在循环中使用双指针方法需要 O ( n 2 ) O(n^2) O(n2)，因此总体时间复杂度为 O ( n 2 ) O(n^2) O(n2)。
-
空间复杂度:
O ( n ) O(n) O(n)- 如果不考虑用于存储输出的空间，空间复杂度为 O ( 1 ) O(1) O(1)。排序是就地完成的，只使用常量量的额外空间。
代码
class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
nums.sort()
result = []
for i in range(len(nums)):
if nums[i] > 0:
break
if i > 0 and nums[i] == nums[i-1]:
continue
l = i+1
r = len(nums) - 1
while l < r:
if nums[i] + nums[l] + nums[r] < 0:
l+=1
elif nums[i] + nums[l] + nums[r] > 0:
r-=1
else:
result.append([nums[i], nums[l], nums[r]])
l+=1
r-=1
while nums[l] == nums[l-1] and l < r:
l+=1
return result