3Sum

Given an integer array nums, return every unique triplet [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0. The result must not contain duplicate triplets (as sets of values), and each triplet should be sorted in ascending order internally. Order the triplets themselves in ascending order by first value, then second value.

Input / output

• Input: nums: integer[]
• Output: integer[][], one inner array per unique triplet, each sorted ascending, outer list sorted ascending

Examples

1. nums = [-1, 0, 1, 2, -1, -4] returns [[-1, -1, 2], [-1, 0, 1]].
2. nums = [0, 1, 1] returns [] because no triplet sums to zero.
3. nums = [0, 0, 0] returns [[0, 0, 0]].

Constraints

• 3 <= nums.length <= 3000
• -100,000 <= nums[i] <= 100,000
• The same value may appear more than once in nums, but each returned triplet must be unique by value.

Follow-up Can you avoid an explicit hash set for de-duplication by sorting the array first and skipping over repeated values while scanning?