3Sum

Medium· sort + two pointers· dedup

Problem

Find all unique triplets in an array whose three values sum to zero. The triplets must use three different indices, and the result must not contain the same triplet twice.

Examples

Input: nums = [-1,0,1,2,-1,-4]

Output: [[-1,-1,2],[-1,0,1]]

These are the only two distinct value-triplets that add to zero.

Input: nums = [1,2,-2,-1]

Output: []

Constraints

• 3 <= nums.length <= 3000
• -10^5 <= nums[i] <= 10^5

Hints & approach

Hint 1

Fix one number; the problem becomes Two Sum on the rest.

Hint 2

Sorting lets you use two pointers for that inner Two Sum and makes duplicates adjacent.

Hint 3

Skip over equal values for the fixed number and for both pointers after a match.

Approachtry the hints first

Sort the array. For each index i (skipping it if nums[i] equals nums[i - 1]), run two pointers on the range after i looking for a pair that sums to -nums[i]. On a match, record the triplet and move both pointers inward past any repeated values. Otherwise move the pointer that brings the sum closer to the target. Sorting costs O(n log n) and the nested scan costs O(n^2).

Time O(n^2) · Space O(1) extra (ignoring sort and output)

← PreviousTwo Sum II - Input Array Is Sorted Next →Container With Most Water