3Sum

medium

Given an integer array nums, return all the triplets [nums[i], nums[j], nums[k]] such that i != j, i != k, j != k, and nums[i] + nums[j] + nums[k] == 0.

Notice that the solution set must not contain duplicate triplets.

Test Cases

Copy an input into the main harness and Run to verify

Input

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

Expected Output

[[-1,-1,2],[-1,0,1]]

Explanation: Both triplets sum to zero. The repeated -1 produces only one distinct triplet.

Input

nums = [0,1,1]

Expected Output

[]

Explanation: No triplet sums to zero.

Input

nums = [0,0,0]

Expected Output

[[0,0,0]]

Constraints

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

Hints

Hint 1 — click to reveal

Sorting makes duplicates adjacent, which is what lets you skip them cleanly.

Hint 2 — click to reveal

Fix the first number, then the problem reduces to Two Sum on a sorted array — solvable with two pointers.

Java Compiler