3Sum

Medium

Two Pointers

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

Notice that the solution set must not contain duplicate triplets.

Example 1

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

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

Explanation: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. The distinct triplets are [-1,0,1] and [-1,-1,2].

Example 2

Input: nums = [0,1,1]

Output: []

Explanation: The only possible triplet does not sum up to 0.

Example 3

Input: nums = [0,0,0]

Output: [[0,0,0]]

Explanation: The only possible triplet sums up to 0.

Constraints

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

Show Hints (3)

Hint 1: Sort the array first. Then fix one element and use two pointers to find pairs that sum to the negative of that element.

Hint 2: Skip duplicate elements to avoid duplicate triplets in the result.

Hint 3: For each fixed element nums[i], use two pointers on the subarray from i+1 to end to find pairs summing to -nums[i].

Loading editor...

Test Results

Click "Run" to execute your code against test cases

AI Tutor

Socratic guidance - I'll ask questions, not give answers

AI Tutor

Hello! I'm your AI tutor, here to guide you through this problem using the Socratic method. I won't give you direct answers, but I'll ask questions and provide hints to help you discover the solution yourself. What's your first instinct when you look at this problem? What approach comes to mind?