3Sum in Python

Given a list of integers nums, return all the triplets [nums[i], nums[j], nums[k]] such that i, j and k are three different indices and nums[i] + nums[j] + nums[k] == 0.

The answer must not contain duplicate triplets: triplets made of the same three values count once, whichever indices they come from.

Write each triplet with its values in ascending order, and return the triplets in ascending order too: compare two triplets by their first value, then by their second, then by their third. Sorting nums first and then collecting the triplets from left to right produces exactly this order, so the answer needs no sorting at the end.

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]. In ascending order, [-1,-1,2] comes first.

Example 2:

Input: nums = [0,1,1]
Output: []
Explanation: The only triplet adds up to 2, not 0.

Example 3:

Input: nums = [0,0,0,0]
Output: [[0,0,0]]
Explanation: Several choices of three indices give 0 + 0 + 0 = 0, but they all form the same triplet, so it appears once.

Constraints:

• 3 <= nums.length <= 3000
• -105 <= nums[i] <= 105