3Sum
Part of Practice: Converging Pairs
Given an integer array nums, return every unique triplet of values that sums to zero. The three elements must come from three different positions, and the output must not contain the same combination of values twice, even if it can be formed from different positions.
The array can hold up to 3,000 values including duplicates and negatives, so an O(n^3) scan of all triples is too slow and duplicate handling is a core part of the problem.
Examples
- Input:
- nums = [-1, 0, 1, 2, -1, -4]
- Output:
- [[-1, -1, 2], [-1, 0, 1]]
Both triplets sum to zero. [-1, 0, 1] is listed once even though it can be built using either of the two -1s.
- Input:
- nums = [0, 1, 1]
- Output:
- []
No three values sum to zero.
- Input:
- nums = [0, 0, 0]
- Output:
- [[0, 0, 0]]
Hints
One at a time — struggle first, peek second.
Your thinking space — verify on LeetCode, then mark it.