Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, and j != k, and nums[i] + nums[j] + nums[k] == 0.
Notice that the solution set must not contain duplicate triplets.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
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.
The distinct triplets are [-1,0,1] and [-1,-1,2].
Notice that the order of the output and the order of the triplets does not matter.
Example 2:
Input: nums = [0,1,1]
Output: []
Explanation: The only possible triplet does not sum up to 0.
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Explanation: The only possible triplet sums up to 0.
思路：双指针
class Solution:def threeSum(self, nums: List[int]) -> List[List[int]]:nums.sort()ans = []n = len(nums)for i in range(n - 2):x = nums[i]if i > 0 and x == nums[i - 1]: # 跳过重复数字continueif x + nums[i + 1] + nums[i + 2] > 0: # 优化一breakif x + nums[-2] + nums[-1] < 0: # 优化二continuej = i + 1k = n - 1while j < k:s = x + nums[j] + nums[k]if s > 0:k -= 1elif s < 0:j += 1else:ans.append([x, nums[j], nums[k]])j += 1while j < k and nums[j] == nums[j - 1]: # 跳过重复数字j += 1k -= 1while k > j and nums[k] == nums[k + 1]: # 跳过重复数字k -= 1return ans