3Sum
Given an array of integers nums, return all possible triplets [nums[i], nums[j], nums[k]] where nums[i] + nums[j] + nums[k] = 0, and the indices i, j, and k are distinct.
The result should not contain duplicate triplets. You can return the triplets in any order.
Example 1:
Input: nums = [-1,0,1,2,-1,-4]
Output: [[-1,-1,2],[-1,0,1]]
Explanation:
nums[0] + nums[2] + nums[1] = (-1) + 1 + 0 = 0
nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0
Example 2:
Input: nums = [0,0,0]
Output: [[0,0,0]]
Recommended time and space complexity
The optimal solution has O(n²) time complexity and O(1) or O(n) space complexity, where n is the size of the input array.
Hint 1
Sorting the array at the beginning can help avoid duplicates and simplify the search for the required triplets.
Hint 2
After sorting, you can use the two-pointer technique for each fixed element to find the remaining two numbers.
Hint 3
To avoid duplicates, skip repeating values when iterating through the fixed element and when moving the pointers.