Approach #1 Brute Force With Extra Space [Time Limit Exceeded]
Algorithm
Each time get three numbers from an array and check if their sum is equal to 0
.
The problem requires to find all unique triplets
; therefore, all duplicates
should be eliminated.
Naive approach to eliminate all duplicates can be storing all triplets in a set.
We also need to consider cases when numbers in triplets are in different positions; consequently,
these numbers will not be considered as duplicates.
Input:
[5,5,4,3,0,0,4,2]
4
Output:
[[5,5,0,4],[5,5,4,0],[5,3,4,2],[5,4,3,2]]
Expected:
[[5,0,4,5],[3,2,4,5]]
Therefore, first we need to sort the array.
sort(nums.begin(), nums.end())
As a result,
Input:
[5,5,4,3,0,0,4,2]
4
Output:
[[5,0,4,5],[3,2,4,5]]
Expected:
[[5,0,4,5],[3,2,4,5]]
C++
vector<vector<int>> threeSum(vector<int>& nums) {
set<vector<int>> tripletSet;
sort(nums.begin(), nums.end());
for(int i = 0; i<nums.size(); i++) {
for(int j = i+1; j<nums.size(); j++) {
for(int k = j+1; k<nums.size(); k++) {
if(nums[i] + nums[j] + nums[k] == 0) {
tripletSet.insert({nums[i], nums[j], nums[k]});
}
}
}
}
vector<vector<int>> triplets(tripletSet.begin(), tripletSet.end());
return triplets;
}
Complexity Analysis

Time complexity : $$O(n^3)$$. Because each of these nested loops executes
n
times andnlogn
to sort the array, the total time complexity is $$O(n^3)$$, where n is a size of an array. 
Space complexity : $$O(n^2)$$. If we assume that resultant array is not considered as additional space we need $$O(n^2)$$ space for storing triplets in a set.
Approach #2 Brute Force With Constant Space [Time Limit Exceeded]
Algorithm
Instead of storing triplets in a set eliminate all duplicates in place.
Each time before choosing a number check it with previous neighbor.
C++
vector<vector<int>> threeSum(vector<int>& nums, int target) {
vector<vector<int>> triplets;
sort(nums.begin(), nums.end());
for(int i = 0; i<nums.size(); i++) {
if(i == 0  nums[i] != nums[i1]) {
for(int j = i+1; j<nums.size(); j++) {
if(j == i+1  nums[j] != nums[j1]) {
for(int k = j+1; k<nums.size(); k++) {
if(k == j+1  nums[k] != nums[k1]) {
if(nums[i] + nums[j] + nums[k] == 0) {
triplets.push_back({nums[i], nums[j], nums[k]});
}
}
}
}
}
}
}
return triplets;
}
Complexity Analysis

Time complexity : $$O(n^3)$$. Because each of these nested loops executes
n
times andnlogn
to sort the array, the total time complexity is $$O(n^3)$$, wheren
is a size of an array. 
Space complexity : $$O(1)$$. If we assume that resultant array is not considered as additional space we did not use any extra space.
Approach #3 Two Pointers [Accepted]
Algorithm
Lets simplify the problem into 2Sum
problem. Now we need to find two numbers from an array such that their sum is equal to given target value. Assuming that the array is sorted the approach to solve the problem in this case would be to run two pointers from the start
and the end
of the array.
Each time check the sum of two numbers at pointers with target value. If the sum is equal to target value it means that numbers are found otherwise increment start
or decrement end
.
while(start<end) {
if(nums[start] + nums[end] = target) {
//Numbers are found
} else if(nums[start] + nums[end] < target) {
start++;
} else {
end;
}
}
In this approach we are traversing the array once therefore time complexity
is $$O(n)$$ where n
is a size of the array.
Lets apply this logic to the initial problem by replacing two inner loops with two pointers.
C++
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> triplets;
sort(nums.begin(), nums.end());
for(int i = 0; i<nums.size(); i++) {
if(i == 0  nums[i] != nums[i1]) {
int l = i+1, r = (int)nums.size()1;
while(l<r) {
if(nums[i] + nums[l] + nums[r] == 0) {
triplets.push_back({nums[i], nums[l], nums[r]});
while(l<r && nums[l] == nums[l+1]) {
l++;
}
while(l<r && nums[r] == nums[r1]) {
r;
}
l++;
r;
} else if(nums[i] + nums[l] + nums[r] < 0) {
l++;
} else {
r;
}
}
}
}
return triplets;
}
Run first loop for our initial number in a triplet and for remaining two numbers run inner loop with two pointers which reduce our time complexity by n
.
In order to eliminate duplicates in resulting array of triplets check current number with previous number if they are the same keep moving pointers.
Complexity Analysis

Time complexity : $$O(n^2)$$. Because each outer loop runs
n
times and two pointers runsn
times as well andnlogn
to sort the array, the total time complexity is $$O(n^2)$$, wheren
is a size of an array. 
Space complexity : $$O(1)$$. If we assume that resultant array is not considered as additional space we did not use any extra space.