难度: 中等
给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，同时还满足 nums[i] + nums[j] + nums[k] == 0 。请
你返回所有和为 0 且不重复的三元组。
注意：答案中不可以包含重复的三元组。
示例 1：
输入：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] 。 注意，输出的顺序和三元组的顺序并不重要。
示例 2：
输入：nums = [0,1,1] 输出：[] 解释：唯一可能的三元组和不为 0 。
示例 3：
输入：nums = [0,0,0] 输出：[[0,0,0]] 解释：唯一可能的三元组和为 0 。
提示：
3 <= nums.length <= 3000-105 <= nums[i] <= 105运行时间: 1152 ms
内存: 18 MB
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort()
ans = []
def twoSum(lo, hi, target):
res = []
while lo < hi:
s = nums[lo] + nums[hi]
left = nums[lo]
right = nums[hi]
if s == target:
res.append([nums[lo], nums[hi]])
while lo < hi and nums[lo] == left:
lo += 1
while lo < hi and nums[hi] == right:
hi -= 1
elif s > target:
while lo < hi and nums[hi] == right:
hi -= 1
else:
while lo < hi and nums[lo] == left:
lo += 1
return res
i = 0
while i < len(nums):
tuples = twoSum(i+1, len(nums)-1, -nums[i])
for t in tuples:
t.append(nums[i])
ans.append(t)
while i+1 < len(nums) and nums[i+1] == nums[i]:
i += 1
i += 1
return ans
这个题解采用排序+双指针的方法解决三数之和问题。首先将整个数组排序，然后遍历数组，对于每个元素，用双指针在该元素右侧的子数组中寻找两个数，使得这三个数的和为0。在寻找的过程中，通过双指针的移动来避免重复的三元组。
时间复杂度: O(n^2)
空间复杂度: O(1)
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
nums.sort() # 对数组排序
ans = []
def twoSum(lo, hi, target):
res = []
while lo < hi:
s = nums[lo] + nums[hi]
left = nums[lo]
right = nums[hi]
if s == target:
res.append([nums[lo], nums[hi]])
while lo < hi and nums[lo] == left: # 跳过重复元素
lo += 1
while lo < hi and nums[hi] == right: # 跳过重复元素
hi -= 1
elif s > target:
while lo < hi and nums[hi] == right: # 跳过重复元素
hi -= 1
else:
while lo < hi and nums[lo] == left: # 跳过重复元素
lo += 1
return res
i = 0
while i < len(nums):
tuples = twoSum(i+1, len(nums)-1, -nums[i]) # 在i右侧寻找两个数，使得三数之和为0
for t in tuples:
t.append(nums[i])
ans.append(t)
while i+1 < len(nums) and nums[i+1] == nums[i]: # 跳过重复元素
i += 1
i += 1
return ans
在实现 `twoSum` 函数时，你是如何确保找到的两个数与当前元素的组合是独一无二的？
在 `twoSum` 函数实现中，为了确保找到的组合是独一无二的，采用了跳过重复元素的策略。当找到一对有效的元素组合后，通过循环检查并跳过与当前元素相同的后续元素，这样可以避免产生重复的三元组。这一操作在找到符合条件的组合后及比较结束时均有实现，确保了组合的唯一性。
为什么在寻找两数之和时，需要跳过重复元素，这种跳过重复元素的操作会影响到算法的正确性吗？
跳过重复元素是为了避免在结果列表中出现重复的三元组，因此这是必要的操作。该操作不会影响算法的正确性，而是保证了答案的正确性和唯一性。如果不跳过重复元素，算法会重复计算已经计算过的数值组合，导致结果中包含重复的三元组。
双指针方法在这里是如何有效地减少搜索空间并避免不必要的计算的？
双指针方法通过同时从序列的两端向中间搜索，有效地减少了搜索空间。当两指针指向的元素和小于目标值时，左指针向右移动；当和大于目标值时，右指针向左移动。这种方法避免了对不可能产生有效结果的组合的检查，从而减少了不必要的计算。
你提到空间复杂度为 O(1)，但是在存储答案时需要额外空间，这部分空间应该如何计算？
虽然算法的空间复杂度为 O(1)，意指除了输出结果以外不需要额外的空间，但在实际应用中，存储答案的空间依赖于答案的数量和大小。因此，这部分空间并不计入算法的空间复杂度中，算法复杂度主要指除了输出所需的存储空间之外的空间使用。
排序步骤是如何帮助优化整个算法流程的，它对双指针法有什么具体的帮助？
排序是优化这种算法的关键步骤，因为排序后的数组允许使用双指针技术有效地搜索。排序保证了数组中的元素是有序的，这使得通过调整指针来增大或减小两数之和成为可能，从而在遍历数组时能够更高效地查找到目标组合。
在整个数组遍历过程中，为什么需要选择固定一个元素并寻找其他两个元素，而不是固定两个元素来寻找第三个元素？
在这种特定的问题中，固定一个元素并在其右侧使用双指针寻找其他两个元素可以更有效地减少搜索空间并避免重复。如果固定两个元素再寻找第三个，会复杂化对重复三元组的检查和排除过程，并可能增加不必要的计算。固定一个元素并对剩余部分进行搜索是一种更高效且易于实现的策略。