3Sum
Problem Description
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:
The distinct triplets are [-1,0,1] and [-1,-1,2].Notice that the order of the output and the order of the triplets does not matter.
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
- -105 <= nums[i] <= 105
Solve it on LeetCode
Approaches
1. Brute Force
The simplest approach is to try every possible triplet in the array and check if their sum is zero. Although this guarantees we find all solutions, it is not efficient.
Intuition:
- We iterate through each element, and for each element, iterate over every pair of subsequent elements.
- We check if the sum of these three elements is zero.
- If the sum is zero, we add the triplet to our list of solutions.
- To ensure we do not add duplicate triplets, we use a set to store the triplets.
Code:
- Time Complexity: O(n^3) - We have three nested loops.
- Space Complexity: O(n) - In the worst case, the set can store all unique triplets.
2. Two Pointers
The two-pointers approach is more efficient. By sorting the array and using two pointers, we reduce the time complexity significantly.
Intuition:
- First, sort the array. This helps in avoiding duplicates and allows the use of two pointers.
- Iterate through the sorted array with an index
i. - For each
i, initialize two pointers:leftati+1andrightat the end of the array. - Calculate the sum of the elements at
i,left, andright. - If the sum is zero, add the triplet to the results and move both pointers inward, skipping duplicates.
- If the sum is less than zero, move the
leftpointer to increase the sum. - If the sum is greater than zero, move the
rightpointer to decrease the sum.
Code:
- Time Complexity: O(n^2) - Sorting the array is O(n log n), and the two-pointers approach takes O(n^2).
- Space Complexity: O(1) - No additional space is used other than the output list.