給你一個整數數組?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

代碼：

from typing import List  # 導入 List 類型，用于類型注解class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:ans = []  # 初始化一個空列表，用于存儲最終的三元組結果nums.sort()  # 將數組排序，方便后續使用雙指針法n = len(nums)  # 獲取數組的長度# 遍歷數組，i 作為三元組的第一個數的索引# 因為需要三個數，所以 i 最多遍歷到倒數第三個數（n-2）for i in range(n - 2):x = nums[i]  # 當前固定的第一個數# 如果當前數 x 和前一個數相同，則跳過本次循環# 這是為了避免重復的三元組if i > 0 and x == nums[i - 1]:continue# 優化：如果當前 x 加上最小的兩個數（nums[i+1] 和 nums[i+2]）已經大于 0# 由于數組是排序的，后面的數只會更大，所以可以直接退出循環if x + nums[i + 1] + nums[i + 2] > 0:break# 優化：如果當前 x 加上最大的兩個數（nums[n-1] 和 nums[n-2]）仍然小于 0# 說明當前 x 太小，即使加上最大的兩個數也無法達到 0，所以跳過當前 xif x + nums[n - 1] + nums[n - 2] < 0:continue# 定義雙指針 j 和 kj = i + 1  # j 從 i 的下一個位置開始k = n - 1  # k 從數組的末尾開始# 使用雙指針法查找滿足條件的三元組while j < k:s = x + nums[j] + nums[k]  # 計算當前三元組的和if s > 0:  # 如果和大于 0，說明需要減小和，將右指針 k 向左移動k -= 1elif s < 0:  # 如果和小于 0，說明需要增大和，將左指針 j 向右移動j += 1else:  # 如果和等于 0，找到一個滿足條件的三元組ans.append([x, nums[j], nums[k]])  # 將三元組加入結果列表j += 1  # 移動左指針k -= 1  # 移動右指針# 跳過重復的 nums[j]，避免重復的三元組while j < k and nums[j] == nums[j - 1]:j += 1# 跳過重復的 nums[k]，避免重復的三元組while k > j and nums[k] == nums[k + 1]:k -= 1return ans  # 返回最終的三元組結果

測試結果

輸入

nums?=

[-1,0,1,2,-1,-4]

輸出

[[-1,-1,2],[-1,0,1]]

預期結果

[[-1,-1,2],[-1,0,1]]