3Sum
给你一个整数列表 nums。找出所有由 nums 中三个不同位置的值组成的三元组 [a, b, c]，使得 a + b + c = 0。将每个三元组按非递减顺序排列（a ≤ b ≤ c），并且每个不同的三元组只列出一次，即使有多种位置组合能组成它。返回的三元组按第一个值排序，相同情况下再按第二个值排序。
函数
- numsinteger-array
- 至少包含 3 个元素的整数列表
- 返回值integer-2d-array
- 每个和为 0 的不同三元组，每个三元组都按非递减顺序排列，列表已排序
约束条件
3 ≤ nums.length ≤ 3000-105 ≤ nums[i] ≤ 105- 至少有一个三元组的和为 0。
- 当两个三元组包含相同的三个值时，它们相同。
示例
- 输入
- nums = [-2, 0, 1, 1, -1, 2]
- 输出
- [[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]
- 解释
- 三个三元组的和为 0。
[-2, 1, 1]中的值 1 使用了两次，因为 1 出现在两个位置；[-1, 0, 1]可以使用任意一个 1，但只出现一次。
- 输入
- nums = [0, 0, 0, 0]
- 输出
- [[0, 0, 0]]
- 解释
- 四个 0 中任意三个相加都等于 0。位置有四种选法，但得到的三元组都相同，因此答案中只保留一次
[0, 0, 0]。
进阶
同样的模式也能解决 4Sum：固定两个值，再对其余元素使用双指针。你能用 O(n³) 实现它，并在每一层都正确处理重复项吗？
提示
逐个打开提示，每个都会多透露一点。
先对列表排序。排序后的列表有两点好处：每个三元组中的值都会按顺序排列，而且相同的值会相邻排列，因此重复值总会紧挨着它重复的值。
固定三元组中最小的值
nums[i]。另外两个值的和必须为-nums[i]，并且它们来自i右侧已排序的值。这是在已排序列表中查找两数之和的问题。对于这一对，从
i后一位开始放置一个指针，并在最后一个索引处放置另一个指针。如果三个值的和小于 0，就将左指针右移；如果大于 0，就将右指针左移。找到匹配项后，移动两个指针，并让左指针跳过值相同的副本。跳过值与前一个相同的i。
题解
检查每个三元组需要 O(n³)，即使值重复，也必须确保每个三元组只出现一次。排序可以同时解决这两个问题：相同的值会相邻排列，因此你可以通过比较相邻元素跳过重复值；固定最小值后，另外两个值就构成了一个有序列表上的两数之和问题。
尝试所有三元组
结果正确，但无法在最大的测试中运行完毕
思路
先对列表排序，然后尝试每三个位置 i < j < k。由于数值按顺序排列，找到三元组时，它的写法就是正确顺序，嵌套循环也不会漏掉任何组合。每个循环都会跳过一个值与该循环上一次尝试的值相同的位置，因此每个不同的三元组只会出现一次。[-2, 1, 1] 仍然会用到两个 1，因为跳过操作只在单个循环内进行比较。
大约有 n³/6 个三元组：n = 3000 意味着有 4.5 × 10^9 个和。
算法
- 对
nums排序。 - 遍历
i，然后从i+1开始遍历j，再从j+1开始遍历k。在每次循环中，如果某个位置的值与该循环之前尝试过的值相同，就跳过该位置。 - 当这三个值的和为 0 时，记录
[nums[i], nums[j], nums[k]]，并按找到的顺序返回这些三元组。
def threeSum(nums):
nums = sorted(nums)
n = len(nums)
triplets = []
for i in range(n - 2):
if i > 0 and nums[i] == nums[i - 1]:
continue # same first value as the round before
for j in range(i + 1, n - 1):
if j > i + 1 and nums[j] == nums[j - 1]:
continue # same second value as the round before
for k in range(j + 1, n):
if k > j + 1 and nums[k] == nums[k - 1]:
continue # same third value as the round before
if nums[i] + nums[j] + nums[k] == 0:
triplets.append([nums[i], nums[j], nums[k]])
return triplets固定一个值，使用哈希集合查找配对项
思路
固定 nums[i] 后，你需要找到两个后面的值，使它们的和等于 -nums[i]：这就是 Two Sum。用一个集合保存已经遍历过的值，让 j 从 i 的右侧开始移动。如果 need = -nums[i] - nums[j] 在集合中，那么 [nums[i], need, nums[j]] 的和就是 0。对于一个 i，平均需要 O(n) 时间，整个搜索需要 O(n²) 时间。
找到匹配项后，让 j 越过 nums[j] 的重复值：第一个值和第三个值固定后，中间的值也就固定了。need 来自排序后更靠前的位置，因此这个三元组是有序的；但随着 j 向右移动，need 会变小：一个 i 会先得到 [-2, 1, 1]，再得到 [-2, 0, 2]。添加前，反转每组中的顺序。
算法
- 对
nums排序。 - 遍历每个
i，当nums[i] > 0时停止；如果nums[i]等于nums[i-1]，则跳过i。 - 创建一个空集合。从
i+1开始遍历每个j，计算need = -nums[i] - nums[j]。如果集合中有need，就记录[nums[i], need, nums[j]]，并让j越过所有与nums[j]相同的元素。 - 将
nums[j]添加到集合中，然后继续遍历下一个j。 - 反转为当前
i找到的三元组，并将它们添加到答案中。
def threeSum(nums):
nums = sorted(nums)
n = len(nums)
triplets = []
for i in range(n - 2):
if nums[i] > 0:
break # the two values after it are at least as large
if i > 0 and nums[i] == nums[i - 1]:
continue # this first value was already handled
group = []
seen = set() # values between position i and position j
j = i + 1
while j < n:
need = -nums[i] - nums[j]
if need in seen:
group.append([nums[i], need, nums[j]])
while j + 1 < n and nums[j + 1] == nums[j]:
j += 1
seen.add(nums[j])
j += 1
# need shrinks as nums[j] grows, so this group came out backwards
group.reverse()
triplets.extend(group)
return triplets排序并使用双指针
思路
固定 nums[i]，将 lo 放在 i+1，将 hi 放在最后一个索引处。如果总和小于 0，那么即使加上剩下的最大值 nums[hi]，nums[lo] 仍然不够大，因此它无法与当前范围内的任何值配对：将 lo 右移。如果总和大于 0，情况正好相反：即使加上剩下的最小值，nums[hi] 仍然太大，因此将 hi 左移。每一步都会永久排除一个值，同时不会漏掉任何三元组，所以每个 i 最多需要 n 步，搜索的时间复杂度为 O(n²)，且不需要额外内存。
重复值需要两条规则。跳过值与前一个值相同的 i。找到匹配项后，让 lo 越过与当前值相同的副本。hi 不需要规则：旧的 nums[hi] 的副本现在会使总和大于 0，因此会自行向左移动。由于 i 按递增顺序遍历不同的值，而 lo 只会向右移动，得到的三元组就是有序的。
算法
- 对
nums排序。 - 遍历每个
i，当nums[i] > 0时停止；如果nums[i]等于nums[i-1]，则跳过i。 - 设置
lo = i+1和hi = n-1。当lo < hi时，将nums[i]、nums[lo]和nums[hi]相加。 - 如果和小于 0，就将
lo向右移动；如果和大于 0，就将hi向左移动。 - 如果和为 0，就记录这个三元组，将两个指针都移动，然后让
lo越过与它所用值相同的副本。
def threeSum(nums):
nums = sorted(nums)
n = len(nums)
triplets = []
for i in range(n - 2):
if nums[i] > 0:
break # the two values after it are at least as large
if i > 0 and nums[i] == nums[i - 1]:
continue # this first value was already handled
lo, hi = i + 1, n - 1
while lo < hi:
total = nums[i] + nums[lo] + nums[hi]
if total < 0:
lo += 1
elif total > 0:
hi -= 1
else:
triplets.append([nums[i], nums[lo], nums[hi]])
lo += 1
hi -= 1
while lo < hi and nums[lo] == nums[lo - 1]:
lo += 1
return triplets
易错点和边界情况
- 当
nums[i]等于nums[i+1]时跳过i。在[-1, -1, 2]中，这样会漏掉[-1, -1, 2]；应与nums[i-1]比较。 - 当
nums[i] ≥ 0时停止，而不是当nums[i] > 0时停止。这样会漏掉[0, 0, 0]。 - 最后才删除重复项。对于 3000 个零，循环会在清理之前记录数百万个
[0, 0, 0]副本。 - 重复使用同一个位置。哈希集合版本如果一开始就把整个列表填入集合，会把
[-2, 1, 3]变成[-2, 1, 1]。 - 忘记在哈希集合版本中反转每组元素。三元组必须按排序后的顺序排列。
常见问题3
3Sum 的时间复杂度是多少？
排序加双指针的解法需要 O(n²) 时间：排序需要 O(n log n)，而第一个值的 n 种选择各需要进行一次 O(n) 遍历。除排序和输出外，它只需要 O(1) 的额外空间。检查每个三元组需要 O(n³) 时间。
对于 3Sum，我应该使用双指针还是哈希集合？
两者的运行时间都是 O(n²)。双指针不需要额外内存，而且会按顺序给你三元组。哈希集合需要 O(n) 内存，并且需要小心处理，确保位置互不相同且输出已排序。当你无法排序时，哈希集合的思路就很重要，例如 Two Sum 中需要返回原始索引。
3Sum 能否用比 O(n²) 更快的方法解决？
差别不大。已知最好的算法只比 n² 快几个对数因子，而且计算几何中的许多困难性结果都假设没有算法能达到低于 2 的 n 的幂次复杂度。面试中通常期待的答案是 O(n²)。
相似题目
运用相同思路的题目。做两三道，才能真正掌握一种模式。
def threeSum(nums):
# 在这里编写代码测试 #1
测试 #2
参数
nums = [-2, 0, 1, 1, -1, 2]
预期输出
[[-2, 0, 2], [-2, 1, 1], [-1, 0, 1]]