Given an integer array nums, return every distinct triplet of values that sums to zero. Each triplet must use three different positions in nums, but two triplets are the same if they hold the same three values — [-1,0,1] is one answer no matter how many ways it can be assembled. Report each triplet in ascending order, and the triplets themselves sorted lexicographically. If nothing sums to zero, return an empty list.
Examples
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation: [-1,0,1] can be formed two ways but counts once.
Example 2:
Input: nums = [0,1,1]
Output: []
Example 3:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Example 4:
Input: nums = [-2,0,1,1,2]
Output: [[-2,0,2],[-2,1,1]]
Constraints
3 <= nums.length <= 3000
-10^5 <= nums[i] <= 10^5
Prerequisites
Two pointers — one pass with an index at each end, and the argument for why moving one of them cannot lose the answer.
How to think about it
1. Sort, Then Two Pointers Optimal
Intuition
Sorting does two jobs at once: it makes the required output order fall out for free, and it turns "find two numbers summing to -x" into a two-pointer walk. Fix the smallest element, then close the remaining pair from both ends — a sum that is too small can only be helped by moving the left pointer up, too large by moving the right pointer down.
Algorithm
1. Sort the array. 2. For each index i, skip it if it repeats the previous value — that would repeat a triplet. 3. Walk left and right pointers over the rest, summing with nums[i]. 4. Too small: move left up. Too large: move right down. Zero: record it. 5. After recording, skip equal neighbours on both sides before stepping inward.
Time & Space
Time O(n^2) — a linear two-pointer pass for each of n starting elements, after an O(n log n) sort. Space O(1) beyond the output.