Two Pointers Pointers from both ends
154. 3Sum
You are given an array of integers nums. Return every triple of values from nums that adds up to
zero. A triple is three elements at three different positions, and you return their values as a list of
three numbers.
Return each triple once. Two triples are the same when they hold the same three values, even if the values
come from different positions or are listed in a different order. A value can appear twice in a triple only
if it appears at least twice in nums, and the same holds for three times.
The triples can come back in any order, and so can the values inside each triple. The examples list each triple's values from smallest to largest and sort the triples.
Example 1
Input: nums = [2, -3, 1, -1, 2, 0, -1]
[[-3,1,2],[-1,-1,2],[-1,0,1]]Explanation: Three triples add up to 0: −3 + 1 + 2, −1 + (−1) + 2 and −1 + 0 + 1. The value 2 appears twice, so −3, 1 and 2 can be picked from two sets of positions, but the triple is listed once.
Example 2
Input: nums = [0, -5, 0, 5, 0]
[[-5,0,5],[0,0,0]]Explanation: −5 + 0 + 5 = 0, and the three zeros add up to 0 as well. Each triple appears once, although there are three zeros to pick from.
Example 3
Input: nums = [2147483647, -2147483648, 1, 0, 0]
[[-2147483648,1,2147483647]]Explanation: The values can be as large as a 32-bit integer allows. Here −2147483648 + 1 + 2147483647 = 0. No other three elements add up to 0, and two zeros are not enough for the triple 0, 0, 0.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 3000-231 ≤ nums[i] ≤ 231 − 1
Clarifying questions
What you would ask an interviewer before writing any code.