You get an integer array nums. Find every group of three numbers, taken from three different positions in the array, that adds up to exactly 0, and return the groups as triplets.
Two triplets that hold the same three values count as one, even when they come from different positions: list each set of values only once. A value can appear twice in a triplet only if it appears at least twice in nums.
You may return the triplets in any order, and the three numbers inside each triplet in any order too.
-4 + 1 + 3, -4 + 2 + 2 and -1 + 0 + 1 all make 0. The triplet [-4,2,2] is allowed because 2 sits at two different positions.
Many choices of positions give -5 + 0 + 5, but they are all the same triplet, so it appears once.
[]
The only possible triplet sums to 3, so there is nothing to return.
Constraints
3 <= nums.length <= 3000-10⁵ <= nums[i] <= 10⁵If the array were sorted, fixing the smallest number of a triplet would leave a simpler question: which two of the numbers after it add up to its negative?
Three numbers are hard to search for at once. One number is easy. So fix one of the three, say a, and the rest of the job is a pair search: find two other numbers that add up to -a. That's the Two Sum problem, run once for each choice of a.
Time O(n²)Space O(1)
The full walkthrough and code are part of Premium