給你一個包含 n 個整數的數組 nums，判斷 nums 中是否存在三個元素 a，b，c ，使得 a + b + c = 0 ？請你找出所有和為 0 且不重復的三元組。
注意：答案中不可以包含重復的三元組。
示例 1：
輸入：nums = [-1,0,1,2,-1,-4]
輸出：[[-1,-1,2],[-1,0,1]]
示例 2：輸入：nums = []
輸出：[]
示例 3：輸入：nums = [0]
輸出：[]
提示：
0 <= nums.length <= 3000
-105 <= nums[i] <= 105
來源：力扣（LeetCode）
鏈接：https://leetcode.cn/problems/3sum
如果我們直接使用三重循環枚舉三元組，會得到 O(N^3)個滿足題目要求的三元組（其中 N 是數組的長度）時間復雜度至少為 O(N^3)。在這之後，我們還需要使用哈希表進行去重操作，得到不包含重復三元組的最終答案，又消耗了大量的空間。這個做法的時間復雜度和空間復雜度都很高，因此我們要換一種思路來考慮這個問題。
我們保持三重循環的大框架不變，只需要保證：
第二重循環枚舉到的元素不小於當前第一重循環枚舉到的元素；
第三重循環枚舉到的元素不小於當前第二重循環枚舉到的元素。
如果我們固定了前兩重循環枚舉到的元素 a 和 b，那麼只有唯一的 c 滿足 a+b+c=0a+b+c=0。當第二重循環往後枚舉一個元素 b′時，由於 b' > b，那麼滿足 a+b'+c'=0 的 c′一定有 c' < c，即 c ′在數組中一定出現在 c 的左側。也就是說，我們可以從小到大枚舉 b，同時從大到小枚舉 c，即第二重循環和第三重循環實際上是並列的關系。
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
n = len(nums)
nums.sort()
ans = list()
# 枚舉 a
for first in range(n):
# 需要和上一次枚舉的數不相同
if first > 0 and nums[first] == nums[first - 1]:
continue
# c 對應的指針初始指向數組的最右端
third = n - 1
target = -nums[first]
# 枚舉 b
for second in range(first + 1, n):
# 需要和上一次枚舉的數不相同
if second > first + 1 and nums[second] == nums[second - 1]:
continue
# 需要保證 b 的指針在 c 的指針的左側
while second < third and nums[second] + nums[third] > target:
third -= 1
# 如果指針重合，隨著 b 後續的增加
# 就不會有滿足 a+b+c=0 並且 b<c 的 c 了，可以退出循環
if second == third:
break
if nums[second] + nums[third] == target:
ans.append([nums[first], nums[second], nums[third]])
return ans復雜度分析
時間復雜度：O(N^2)，其中 N 是數組nums 的長度。
空間復雜度：O(logN)。我們忽略存儲答案的空間，額外的排序的空間復雜度為 O(logN)。然而我們修改了輸入的數組nums，在實際情況下不一定允許，因此也可以看成使用了一個額外的數組存儲了nums 的副本並進行排序，空間復雜度為 O(N)。
