Fix one number, and "find three numbers that sum to zero" becomes "find two numbers that sum to a target" on the rest, which you already solved with two pointers on a sorted list. Sorting first also makes duplicate triplets easy to skip.
Given a list of integers nums, return all unique triplets [a, b, c] of elements (at distinct indices) such that a + b + c == 0. Triplets may be returned in any order, and the numbers within a triplet may be in any order, but the same triplet must not appear twice.
Examples
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Input: nums = [0, 1, 1]
Output: []
Input: nums = [0, 0, 0]
Output: [[0, 0, 0]]
Constraints
0 <= len(nums) <= 500- Aim for O(n²) time. The brute-force O(n³) triple loop with a set of tuples works on small inputs but is the wrong habit to build.
Goals
- Reduce a three-element problem to a two-pointer search by fixing one element
- Sort first so that duplicates are adjacent and can be skipped
- Produce every unique triplet exactly once