Problem
3Sum
Medium- arrays
- two-pointers
Find every set of three numbers in nums, taken from three different positions, that add up to 0. Each triplet of values goes in the result once, even when it can be built from several positions.
Write each triplet from smallest value to largest, and list the triplets in ascending order (by first value, then second, then third). If no triplet adds up to 0, return an empty array.
- Input
nums = [3, -1, -1, -1, 2, 0, -2, 1]- Output
[[-2, -1, 3], [-2, 0, 2], [-1, -1, 2], [-1, 0, 1]]- Explanation
-2 + -1 + 3,-2 + 0 + 2,-1 + -1 + 2and-1 + 0 + 1all make0. The three-1values could form[-1, 0, 1]in three ways and[-1, -1, 2]in three ways, but each is listed once.
- Input
nums = [1, 2, 3, 4]- Output
[]- Explanation
every number is positive, so no three of them can add up to
0.
- Input
nums = [0, 0, 0, 0]- Output
[[0, 0, 0]]- Explanation
there are four ways to pick three of the zeros, but they all give the same triplet, so it is listed once.
Constraints:
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Follow-up: checking every triplet takes O(n^3). Can you get it down to O(n^2)?
Tab indents. Press Esc, then Tab to leave the editor.
Run your code to see every test here. Nothing is submitted or recorded.