#15 3Sum
Given an integer array nums, return every triplet of values
[nums[i], nums[j], nums[k]] (three distinct positions) that sums to zero.
The output must contain no duplicate triplets: two triplets with the same three values in any order count as the same triplet, no matter which indices produced them. Return the triplets in any order.
Examples
nums = [-1, 0, 1, 2, -1, -4][[-1, -1, 2], [-1, 0, 1]]Both -1's can pair with 2, and -1/0/1 also cancels, but each value-triplet appears once, however many index combinations produce it.
nums = [0, 1, 1][]No three values cancel to zero.
nums = [0, 0, 0][[0, 0, 0]]Three distinct positions, one valid value-triplet.
Constraints
3 ≤ nums.length ≤ 3000-10⁵ ≤ nums[i] ≤ 10⁵
The explainer is the good part.
Sign in for the full intuition build-up, every approach from naive to optimal with complexity analysis, progressive hints, and commented solutions in Python, JavaScript, and Java. All free.
Want a taste first? Try a free sample: Two Sum or Valid Parentheses.