Back to Arrays3Sum
Medium

3Sum

MediumMust DoTwo PointersHashing

Given an array of integers, find all unique triplets that sum to zero. Each triplet's values are returned in ascending order, and the result must not contain duplicate triplets.

Examples

Example 1

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

Explanation: Sorting first groups duplicates together, so fixing each distinct starting value once and sweeping the rest with two pointers finds both triplets without repeats.

Example 2

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

Explanation: No three values in the array sum to zero.

Example 3

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

Explanation: Even though the array holds three copies of the same value, only one triplet is returned — it's duplicate triplets that are eliminated, not duplicate values within a valid triplet.

Constraints

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

Follow-up

How would you adapt this approach to find all unique quadruples (4Sum) that sum to a target?

Loading editor…

Code execution is coming soon.