All problems

3Sum

Medium · two pointers

Given a list of integers nums, return every set of three numbers (at three different positions) that add up to 0.

The answer must be unique. Write each triplet in ascending order, for example [-1, 0, 1] and never [0, -1, 1]. Do not list the same triplet twice, even if its values appear at several positions in nums. The triplets themselves may be returned in any order. If no triplet sums to 0, return an empty list.

Examples

Example 1

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

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

-1 + -1 + 2 = 0 and -1 + 0 + 1 = 0. The two -1 values give [-1, 0, 1] in two ways, but we list it once.

Example 2

Input: nums = [0, 1, 1]

Output: []

The only sum is 0 + 1 + 1 = 2, so there is no triplet.

Example 3

Input: nums = [0, 0, 0, 0]

Output: [[0, 0, 0]]

Many position choices give the same triplet, but it is listed once.

Constraints