Given an array nums of n integers, find all unique triplets in the array that sum up to zero. Each triplet must be in non-descending order (i.e., the elements of each triplet must be in non-decreasing order).
The solution set must not contain duplicate triplets.
Table of Contents
Sample Input and Expected Output:
Input:
nums = [-1, 0, 1, 2, -1, -4]
Output:
Unique triplets that sum up to zero:
[
[-1, -1, 2],
[-1, 0, 1]
]
3 Sum Solution in C++:
The idea is to use a two-pointer approach along with sorting the array. First, we sort the input array. Then, for each element nums[i], we use two pointers, left and right, to find all the unique triplets that sum up to zero. We skip duplicate elements to avoid duplicate triplets.
#include <iostream>
#include <vector>
#include <algorithm>
std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
std::vector<std::vector<int>> result;
int n = nums.size();
// Sort the input array.
std::sort(nums.begin(), nums.end());
for (int i = 0; i < n - 2; i++) {
// Skip duplicate elements to avoid duplicate triplets.
if (i > 0 && nums[i] == nums[i - 1]) {
continue;
}
int left = i + 1;
int right = n - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
// Found a triplet that sums up to zero.
result.push_back({nums[i], nums[left], nums[right]});
// Skip duplicate elements to avoid duplicate triplets.
while (left < right && nums[left] == nums[left + 1]) {
left++;
}
while (left < right && nums[right] == nums[right - 1]) {
right--;
}
left++;
right--;
} else if (sum < 0) {
left++; // Increment left pointer for a larger sum.
} else {
right--; // Decrement right pointer for a smaller sum.
}
}
}
return result;
}
int main() {
std::vector<int> nums = {-1, 0, 1, 2, -1, -4};
std::vector<std::vector<int>> result = threeSum(nums);
std::cout << "Unique triplets that sum up to zero:" << std::endl;
for (const auto& triplet : result) {
std::cout << "[";
for (int num : triplet) {
std::cout << num << " ";
}
std::cout << "]" << std::endl;
}
return 0;
}
Time Complexity and Space Complexity:
The time complexity of the solution is O(n^2), where n is the size of the nums vector. The sorting step takes O(n log n), and for each element in the array, we perform a two-pointer approach, which takes O(n) in the worst case. Therefore, the overall time complexity is dominated by the two-pointer approach.
The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The output vector, result, grows with the number of unique triplets, but it is not considered in the space complexity analysis since it is part of the function’s return value.