3Sum

Problem

Given an integer array nums, return every distinct triple of values [a, b, c] taken from three different positions such that a + b + c == 0. Two triples are the same if they contain the same multiset of values, regardless of order or which indices produced them. The output may be in any order.

• nums holds between 3 and 4,000 integers.
• Each value lies between -50,000 and 50,000.

Examples

• nums = [3, -2, 1, -1, 4, -5, 2] → [[-5, 1, 4], [-5, 2, 3], [-2, -1, 3]]. Three distinct value triples sum to zero; [-5, 1, 4] and [-5, 2, 3] share the anchor -5.
• nums = [-3, -3, 6, 6, 0, 3] → [[-3, -3, 6], [-3, 0, 3]]. The two -3 values sit at different positions, so they can both appear in one triple, but that triple is reported once even though there are two 6s to pair with.
• nums = [2, 4, 6, 8] → []. Every value is positive, so no triple can sum to zero.

Hints

1. If you fix the first element, what does the remaining problem look like?
2. Sorting the array first turns the remaining problem into something you can solve with two pointers in linear time.
3. Sort, iterate the anchor index, run two-pointer 2Sum on the suffix, and skip over repeated values at each of the three positions to avoid duplicate triples.