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: nums[0] + nums[1] + nums[2] = (-1) + 0 + 1 = 0. nums[1] + nums[2] + nums[4] = 0 + 1 + (-1) = 0. nums[0] + nums[3] + nums[4] = (-1) + 2 + (-1) = 0. 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
Problem Description
This problem asks us to find all the unique triplets in an array that can combine to give a sum of zero. A triplet in this context is defined as a set of three numbers [nums[i], nums[j], nums[k]] where each number comes from a different position in the array, indicated by i, j, and k. Importantly, we need to ensure that:
- The indices
i,j, andkare all different. - The sum of the numbers at those indices is zero (
nums[i] + nums[j] + nums[k] == 0). - No triplet is repeated in the result.
Our goal is to identify all such combinations, ensuring that each combination of three numbers is unique within the result set. This problem is a classic example of a challenge involving array manipulation and the identification of specific patterns within a numerical set.
Intuition
To arrive at the solution for this problem, we will follow a two-step approach. First, we sort the array in non-decreasing order. The sorting helps us in two ways: it makes it easy to avoid adding duplicate triplets and allows us to use the two-pointer technique effectively.
After sorting, the array is processed with a loop that effectively tries out each number as a potential candidate for the first number of the triplet. This candidate is referred to as nums[i]. Starting from i = 0, we will check whether nums[i], when added to any two other numbers in the array to its right, sums to zero.
To expedite the process and avoid checking combinations that are guaranteed to fail or are redundant, we make use of the following insights:
- If the current number
nums[i]is greater than zero, because the array is sorted, any combination involving this and subsequent numbers will be greater than zero. Since no sum with a positive total can equal zero, we can break out of the loop early. - If
nums[i]is the same as the previous numbernums[i-1], we skip the current value to prevent processing the same triplet scenario, which would lead to duplicates.
Once a valid nums[i] is chosen, we employ a while loop using two pointers, j and k, that start after i (for j) and at the end of the array (for k). We calculate the sum of nums[i], nums[j], and nums[k]. If the sum is:
- Less than zero, we move
jto the right to increase the sum (nums[j]will be larger). - Greater than zero, we shift
kto the left to decrease the sum (becausenums[k]will get smaller). - Exactly zero, we have found a valid triplet and add it to our solution set. We then move both
jandkpointers, skipping over any duplicates to look for additional triplets starting withnums[i].
We repeat this process for every index i until the second last element, and collect all unique triplets that give us a sum of zero.
Solution Approach
The code implements a sort and two-pointer strategy to find all unique triplets summing to zero in the nums array. Below are the detailed steps taken by the implementation, following the Reference Solution Approach:
- Sort the Array: First, we sort the array using
nums.sort(). Sorting is beneficial as it orders the elements, allowing us to employ the two-pointer method effectively, and it makes it easier to avoid duplicates since duplicate values will be adjacent in a sorted array. - Iterate Over Possible First Elements of Triplets: We look at each number in the
numsarray (up until the third-to-last element) to be the potential first element of our triplet. This is achieved with a for loop:for i in range(n - 2). - Early Breaks and Continues: Inside this loop, we have some conditions that help us eliminate unnecessary checks:
- If the current number
nums[i]is greater than zero, we can break out of the loop. This is because any triplet involving a positive starting number will have a sum greater than zero. - If the current number is the same as the previous number (and
iis not 0), we usecontinueto skip to the next iteration to avoid checking for duplicates.
- If the current number
- Two-Pointer Technique: For each
i, we use two pointers,jandk, initialized toi + 1andn - 1(the end of the array), respectively. We then enter a while loop, which will continue as long asjis less thank. - Find the Triplets: Within the while loop, we calculate the sum
xofnums[i],nums[j], andnums[k]and compare it to zero:- If
xis less than zero, we incrementjsince we need a larger number to increase the sum. - If
xis greater than zero, we decrementkas we need a smaller number to decrease the sum. - If
xis zero, we have found a valid triplet and we add[nums[i], nums[j], nums[k]]toans. After storing the triplet, we move bothjandkpast any duplicates to ensure we don’t find duplicates in subsequent iterations.
- If
- Return the Result: Once all numbers have been considered for the first element of the triplet, and all valid
j,kpairs have been evaluated, we returnans. This list contains all the unique triplets that add up to zero.
This solution has a time complexity of O(n^2) and a space complexity of O(log n) due to the sort operation, assuming that the sort() method used takes O(log n) space for the internal stack during a sorting algorithm like quicksort or mergesort. However, if the sorting does not take extra space, then the space complexity will only be O(1), which is the space taken by the output array and the pointers used.
Example Walkthrough
Let’s walk through the solution approach using a small example. Consider the array nums = [-1, 0, 1, 2, -1, -4].
Following the steps in the solution approach:
- Sort the Array: We start by sorting
nums, resulting in[-4, -1, -1, 0, 1, 2]. - Iterate Over Possible First Elements of Triplets: We start looking through the array for potential first elements of the triplet. The loop runs from the start of the array to
n - 3, wherenis the length of the sorted nums array. - Early Breaks and Continues: As we loop through, if we find a number larger than zero (
nums[i] > 0), we can break out of the loop. In our example, all numbers from the index 0 ton - 3will be considered since the break condition does not become true.
We also skip the second element, which is -1, same as the first, using continue to avoid duplicates.
- Two-Pointer Technique: We start the two-pointer process with
i,j, andkas follows:i = 0: We choose-4as the first element.j = i + 1:jstarts at-1(the element right after-4).k = n - 1:kstarts at2(the last element).
- Find the Triplets: In the while loop, we find sums of
nums[i] + nums[j] + nums[k]and adjustjandkaccordingly:- The first sum is
-4 + -1 + 2 = -3, which is less than zero. We incrementjto move to the next larger number, which is another-1. - Now, the sum is
-4 + -1 + 2 = -3, still less than zero. We incrementjagain and move to0. - With
jon0, the sum is-4 + 0 + 2 = -2, and we continue incrementingjto move to1. - The sum is now
-4 + 1 + 2 = -1, which is still less than zero, so we movejagain, but now we’ve reached the end, and the while loop ends for thisi.
- The first sum is
Next, with i = 1, we find:
i = 1(but this is skipped because it’s the same asi = 0).i = 2, we have the first element as-1,j = 3andk = 5, so we test the combination-1 + 0 + 2, which sums to1. The sum is greater than zero, so we decrementk.- Now,
kis4, andjis3, so we test-1 + 0 + 1, which sums to0. We’ve found a valid triplet[-1, 0, 1].
Each time we find a triplet, we move both j and k while they point to the same number to avoid duplicates. In this case, there are no duplicates, and we are done with this iteration.
- Return the Result: After evaluating all potential starting points, the solution returns the list of unique triplets found. In this case,
[[-1, 0, 1]]is the only unique triplet that sums to zero.
The implementation would return [[−1, 0, 1]] as the output.
Following the outlined process, we can find all possible unique triplets in the array that can combine to give a sum of zero.
Solution Implementation
class Solution {
public:
// Function to find all unique triplets in an array that sum to zero
vector<vector<int>> threeSum(vector<int>& nums) {
// Result vector to store the triplets
vector<vector<int>> res;
int n = nums.size();
// Set to store unique triplets (avoids duplicates)
set<vector<int>> st;
// Sort the input array to use the two-pointer technique
sort(nums.begin(), nums.end());
// Loop through the array up to the third-to-last element
for (int i = 0; i < n - 2; i++) {
// Set two pointers: one starting from the element after 'i' (start), and one from the last element (end)
int start = i + 1;
int end = n - 1;
// Target sum we are looking for (negation of the current element nums[i])
int target = nums[i] * (-1);
// Two-pointer approach to find pairs that sum to 'target'
while (start < end) {
if (nums[start] + nums[end] == target) {
// If the sum is equal to the target, we found a valid triplet
st.insert({nums[i], nums[start], nums[end]});
start++;
end--;
} else {
// If the sum is greater than the target, move the end pointer left
if (nums[start] + nums[end] > target) {
end--;
} else {
// If the sum is less than the target, move the start pointer right
start++;
}
}
}
}
// Convert the set of unique triplets to a vector
for (vector<int> v : st) {
res.push_back(v);
}
// Return the list of unique triplets
return res;
}
};Copied!
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
// Sort the array to make it easier to find unique triplets
Arrays.sort(nums);
int n = nums.length;
int i = 0;
List<List<Integer>> arr = new ArrayList<>();
// Iterate through the array to find potential triplets
while (i < n - 2) {
// Skip duplicates for the first number in the triplet
if (i > 0 && nums[i] == nums[i - 1]) {
i++;
continue;
}
// Initialize two pointers: one at the next element, one at the end of the array
int j = i + 1;
int k = n - 1;
// Search for two other numbers that sum with nums[i] to make zero
while (j < k) {
int total = nums[i] + nums[j] + nums[k];
// If the sum is greater than zero, move the right pointer left
if (total > 0) {
k--;
}
// If the sum is less than zero, move the left pointer right
else if (total < 0) {
j++;
}
// If the sum is zero, we found a triplet
else {
arr.add(Arrays.asList(nums[i], nums[j], nums[k]));
j++;
// Skip duplicates for the second number in the triplet
while (nums[j] == nums[j - 1] && j < k) {
j++;
}
}
}
// If nums[i] is greater than zero, no valid triplets can be found
if (nums[i] > 0) return arr;
// Move to the next element for the first number in the triplet
i++;
}
// Return the list of unique triplets
return arr;
}
}Copied!
class Solution:
def threeSum(self, nums: List[int]) -> List[List[int]]:
# Set the target sum to 0
target = 0
# Sort the input list to facilitate the two-pointer approach
nums.sort()
# Initialize a set to store unique triplets
s = set()
# Initialize the output list to store the final triplets
output = []
# Iterate through the sorted list
for i in range(len(nums)):
# Set pointers: j starts just after i, k starts at the end of the list
j = i + 1
k = len(nums) - 1
# Use two-pointer approach to find valid triplets
while j < k:
# Calculate the sum of the current triplet
sum = nums[i] + nums[j] + nums[k]
# If the sum is equal to target (0), add the triplet to the set
if sum == target:
s.add((nums[i], nums[j], nums[k]))
j += 1 # Move left pointer right
k -= 1 # Move right pointer left
# If the sum is less than target, increase the left pointer to increase the sum
elif sum < target:
j += 1
# If the sum is greater than target, decrease the right pointer to decrease the sum
else:
k -= 1
# Convert the set of unique triplets into a list
output = list(s)
# Return the final list of unique triplets
return outputCopied!
#include <stdlib.h>
// Comparison function for qsort to sort the array in ascending order
int cmp(const void *a,const void *b) {
return *((int*) a) - *((int*) b);
}
int** threeSum(int* nums, int numsSize, int* returnSize, int** returnColumnSizes){
// Sort the array in ascending order
qsort(nums, numsSize, sizeof(int), cmp);
// Initialize the return size to 0
(*returnSize) = 0;
// Allocate memory for the return column sizes (one for each triplet)
(*returnColumnSizes) = (int*) malloc(sizeof(int) * numsSize * numsSize);
// Allocate memory for the result array to store triplets
int **ret = (int**) malloc(sizeof(int*) * numsSize * numsSize);
// Iterate through the array, looking for triplets that sum to zero
for (int i = 0; i < numsSize - 2; i++) {
// Skip duplicate elements to avoid repeating the same triplet
if (i == 0 || nums[i] != nums[i-1]) {
// Set left pointer (l) to i+1 and right pointer (r) to the last index
int l = i + 1;
int r = numsSize - 1;
// Use the two-pointer technique to find pairs that sum to the target
while (l < r) {
// If the sum of nums[i], nums[l], and nums[r] is less than zero, move the left pointer
if (nums[i] + nums[l] + nums[r] < 0) {
l++;
}
// If the sum is greater than zero, move the right pointer
else if (nums[i] + nums[l] + nums[r] > 0) {
r--;
}
// If the sum equals zero, we have found a valid triplet
else {
// Allocate memory for the current triplet and store it
ret[(*returnSize)] = (int*) malloc(sizeof(int) * 3);
(*returnColumnSizes)[(*returnSize)] = 3;
ret[(*returnSize)][0] = nums[i];
ret[(*returnSize)][1] = nums[l];
ret[(*returnSize)][2] = nums[r];
// Increment the return size and move the left pointer
(*returnSize)++;
l++;
// Skip duplicate values for nums[l] to avoid repeating triplets
while (l < r && nums[l] == nums[l-1])
l++;
}
}
}
}
// Return the result array of triplets
return ret;
}Copied!
public class Solution {
// Main function to find all unique triplets that sum to zero
public IList<IList<int>> ThreeSum(int[] nums)
{
var results = new List<IList<int>>(); // List to store the results
if (nums.Length < 3) return results; // If there are less than 3 numbers, no triplet can be formed
// Shuffle the array to improve the chances of faster sorting and avoid bias
Suffle(nums);
// Sort the array using a 3-way quick sort
Quick3WaySort(nums, 0, nums.Length - 1);
// If the first number is greater than 0, no valid triplet can be found
if (nums[0] > 0) return results;
// If the last number is less than 0, no valid triplet can be found
if (nums[nums.Length - 1] < 0) return results;
// Iterate through the array to find triplets
for (int i = 0; i < nums.Length - 2 && nums[i] <= 0; i++)
{
int lo = i + 1, hi = nums.Length - 1;
// Use two pointers to find pairs that sum with nums[i] to zero
while (lo < hi && nums[hi] >= 0)
{
var sum = nums[i] + nums[lo] + nums[hi];
if (sum < 0) // If the sum is less than zero, move the left pointer to the right
do
lo++;
while (lo < hi && nums[lo - 1] == nums[lo]); // Skip duplicate numbers
else if (sum > 0) // If the sum is greater than zero, move the right pointer to the left
do
hi--;
while (lo < hi && nums[hi] == nums[hi + 1]); // Skip duplicate numbers
else // If the sum is zero, we've found a valid triplet
{
results.Add(new List<int>() { nums[i], nums[lo], nums[hi] });
// Skip duplicate numbers on both left and right sides
do
lo++;
while (lo < hi && nums[lo - 1] == nums[lo]);
do
hi--;
while (lo < hi && nums[hi] == nums[hi + 1]);
}
}
// Skip duplicate values for nums[i] to avoid repeating triplets
while (i < nums.Length - 2 && nums[i] == nums[i + 1])
i++;
}
return results; // Return the list of unique triplets
}
// Helper function to shuffle the array to help with sorting performance
void Suffle(int[] nums)
{
var random = new Random();
int N = nums.Length;
int r, temp;
// Fisher-Yates shuffle algorithm
for (int i = 0; i < N; i++)
{
r = random.Next(i + 1);
temp = nums[r];
nums[r] = nums[i];
nums[i] = temp;
}
}
// Helper function to perform a 3-way quick sort
void Quick3WaySort(int[] nums, int lo, int hi)
{
if (lo >= hi) { return; } // Base case for recursion
var lt = lo;
var gt = hi;
var i = lo;
var v = nums[i]; // Pivot element
int temp;
// 3-way partitioning
while (i <= gt)
{
if (nums[i] > v) // If the current element is greater than the pivot, swap it with the high pointer
{
temp = nums[i];
nums[i] = nums[gt];
nums[gt--] = temp;
}
else if (nums[i] < v) // If the current element is less than the pivot, swap it with the low pointer
{
temp = nums[i];
nums[i] = nums[lt];
nums[lt++] = temp;
}
else { i++; } // If the current element equals the pivot, just move the pointer
}
// Recursively sort the left and right partitions
Quick3WaySort(nums, lo, lt - 1);
Quick3WaySort(nums, gt + 1, hi);
}
}Copied!
var threeSum = function (nums) {
// Sort the array in ascending order
nums.sort((a, b) => a - b);
// Initialize an empty array to store the results
const op = [];
// Iterate through each element in the sorted array
for (let i = 0; i < nums.length; i++) {
// Skip duplicate elements to avoid repeating results
if (i > 0 && nums[i] === nums[i - 1]) continue;
// Set the target sum to be the negative of the current element
const target = -nums[i];
// Initialize two pointers: left and right
let left = i + 1, right = nums.length - 1;
// Use the two-pointer technique to find pairs that sum to the target
while (left < right) {
// Calculate the sum of the elements at the left and right pointers
const current_sum = nums[left] + nums[right];
// If the sum matches the target, we've found a valid triplet
if (current_sum === target) {
op.push([nums[i], nums[left], nums[right]]); // Add the triplet to the result array
// Skip duplicate elements to avoid repeating the same pair
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
// Move the pointers inward to continue searching
left++;
right--;
}
// If the sum is smaller than the target, move the left pointer to the right
else if (current_sum < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left
else {
right--;
}
}
}
// Return the array of triplets that sum to zero
return op;
};Copied!
function threeSum(nums: number[]): number[][] {
// Sort the array in ascending order
nums.sort((a, b) => a - b);
// Initialize an empty array to store the result triplets
const op: number[][] = [];
// Iterate through each element in the sorted array
for (let i = 0; i < nums.length; i++) {
// Skip duplicate elements to avoid repeating the same triplet
if (i > 0 && nums[i] === nums[i - 1]) continue;
// Set the target sum to be the negative of the current element
const target = -nums[i];
// Initialize two pointers: left and right
let left = i + 1, right = nums.length - 1;
// Use the two-pointer technique to find pairs that sum to the target
while (left < right) {
// Calculate the sum of the elements at the left and right pointers
const current_sum = nums[left] + nums[right];
// If the sum matches the target, we've found a valid triplet
if (current_sum === target) {
op.push([nums[i], nums[left], nums[right]]); // Add the triplet to the result array
// Skip duplicate elements to avoid repeating the same pair
while (left < right && nums[left] === nums[left + 1]) left++;
while (left < right && nums[right] === nums[right - 1]) right--;
// Move the pointers inward to continue searching for other pairs
left++;
right--;
}
// If the sum is smaller than the target, move the left pointer to the right
else if (current_sum < target) {
left++;
}
// If the sum is greater than the target, move the right pointer to the left
else {
right--;
}
}
}
// Return the array of triplets that sum to zero
return op;
}Copied!
class Solution {
/**
* @param Integer[] $nums
* @return Integer[][]
*/
function threeSum($nums) {
$result = []; // Initialize an empty array to store the result triplets
$length = count($nums); // Get the length of the input array
// If there are less than 3 elements, return an empty result (no triplets possible)
if ($length < 3) {
return $result;
}
sort($nums); // Sort the array in ascending order to use the two-pointer technique
// Iterate through the sorted array to find triplets
for ($i = 0; $i < $length - 2; $i++) {
// Skip duplicate elements to avoid repeating triplets
if ($i > 0 && $nums[$i] === $nums[$i - 1]) {
continue;
}
// Initialize two pointers: one at the next element after i (left) and the other at the last element (right)
$left = $i + 1;
$right = $length - 1;
// Use the two-pointer technique to find pairs that sum with nums[i] to zero
while ($left < $right) {
$sum = $nums[$i] + $nums[$left] + $nums[$right]; // Calculate the sum of the current triplet
// If the sum is zero, we've found a valid triplet
if ($sum === 0) {
$result[] = [$nums[$i], $nums[$left], $nums[$right]]; // Add the triplet to the result array
// Skip duplicate elements on both the left and right to avoid repeating the triplet
while ($left < $right && $nums[$left] === $nums[$left + 1]) {
$left++;
}
while ($left < $right && $nums[$right] === $nums[$right - 1]) {
$right--;
}
// Move both pointers inward after adding the triplet
$left++;
$right--;
} elseif ($sum < 0) {
// If the sum is less than zero, move the left pointer to the right to increase the sum
$left++;
} else {
// If the sum is greater than zero, move the right pointer to the left to decrease the sum
$right--;
}
}
}
return $result; // Return the array of unique triplets
}
}Copied!
class Solution {
func threeSum(_ nums: [Int]) -> [[Int]] {
// Sort the array in ascending order
let sortedNums = nums.sorted()
// Create a set to store unique triplets
var sums: Set<[Int]> = [ ]
// Iterate through the sorted array to find triplets
for (index, num) in sortedNums.enumerated() {
// If the current number is greater than 0, no valid triplet can be formed
guard sortedNums[index] <= 0 else { break }
// Skip duplicate elements to avoid repeating the same triplet
guard index == 0 || sortedNums[index] != sortedNums[index - 1] else { continue }
// Initialize the two-pointer technique: left pointer just after the current element, right pointer at the end
var left = index + 1
var right = nums.count - 1
// Use two pointers to find pairs that sum with the current number to zero
while left < right {
let sum = sortedNums[left] + sortedNums[right]
// If the sum of the two pointers equals the negative of the current number, a valid triplet is found
if sum == -num {
sums.insert([num, sortedNums[left], sortedNums[right]]) // Add the triplet to the set
left += 1 // Move the left pointer to the right
right -= 1 // Move the right pointer to the left
} else if sum < -num {
// If the sum is smaller than the target, move the left pointer to the right to increase the sum
left += 1
} else {
// If the sum is greater than the target, move the right pointer to the left to decrease the sum
right -= 1
}
}
}
// Convert the set of unique triplets to an array and return it
return Array(sums)
}
}Copied!
class Solution {
fun threeSum(nums: IntArray): List<List<Int>> {
val res = mutableListOf<List<Int>>() // List to store the resulting triplets
nums.sort() // Sort the array to apply two-pointer technique
// Iterate through the sorted array to find triplets
for (i in nums.indices) {
val a = nums[i]
// Skip duplicates of the current number to avoid repeating triplets
if (i > 0 && a == nums[i - 1]) continue
// Initialize the left pointer (just after the current element) and the right pointer (at the end of the array)
var left = i + 1
var right = nums.size - 1
// Use the two-pointer technique to find pairs that sum with 'a' to zero
while (left < right) {
val threeSum = a + nums[left] + nums[right]
when {
threeSum > 0 -> right-- // If the sum is greater than zero, move the right pointer to the left to decrease the sum
threeSum < 0 -> left++ // If the sum is less than zero, move the left pointer to the right to increase the sum
else -> {
res.add(listOf(a, nums[left], nums[right])) // If the sum is zero, add the triplet to the result list
left++ // Move the left pointer to the right to find the next potential triplet
// Skip duplicates of the number at the left pointer to avoid repeating triplets
while (nums[left] == nums[left - 1] && left < right) {
left++
}
}
}
}
}
return res // Return the list of unique triplets
}
}Copied!
class Solution {
List<List<int>> threeSum(List<int> nums) {
nums.sort(); // Sort the array in ascending order to apply the two-pointer technique
List<List<int>> result = []; // List to store the resulting triplets
// Iterate through the array to find the first element of the triplet
for (int i = 0; i < nums.length - 2; i++) {
// Skip duplicate elements to avoid repeating the same triplet
if (i == 0 || (i > 0 && nums[i] != nums[i - 1])) {
int left = i + 1; // Initialize the left pointer (just after the current element)
int right = nums.length - 1; // Initialize the right pointer (at the end of the array)
int target = -nums[i]; // Find two numbers that sum up to -nums[i] to make the total sum zero
// Use the two-pointer technique to find pairs that sum with nums[i] to zero
while (left < right) {
// If the sum of the pair is equal to the target, we've found a valid triplet
if (nums[left] + nums[right] == target) {
result.add([nums[i], nums[left], nums[right]]); // Add the triplet to the result list
// Skip duplicate elements on both sides to avoid repeating the same triplet
while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates on the left
while (left < right && nums[right] == nums[right - 1]) right--; // Skip duplicates on the right
left++; // Move the left pointer to the right
right--; // Move the right pointer to the left
} else if (nums[left] + nums[right] < target) {
left++; // If the sum is less than the target, move the left pointer to the right to increase the sum
} else {
right--; // If the sum is greater than the target, move the right pointer to the left to decrease the sum
}
}
}
}
return result; // Return the list of unique triplets
}
}Copied!
func threeSum(nums []int) [][]int {
var results [][]int // Initialize a slice to store the result triplets
sort.Ints(nums) // Sort the array to apply the two-pointer technique
// Iterate through the sorted array to find the first element of the triplet
for i := 0; i < len(nums)-2; i++ {
// Skip duplicate elements to avoid repeating triplets
if i > 0 && nums[i] == nums[i-1] {
continue // To prevent the repeat of the same triplet
}
// Calculate the target value and initialize left and right pointers
target, left, right := -nums[i], i+1, len(nums)-1
// Use two pointers to find pairs that sum with nums[i] to zero
for left < right {
sum := nums[left] + nums[right] // Calculate the sum of the two pointers
if sum == target {
// If the sum equals the target, a valid triplet is found
results = append(results, []int{nums[i], nums[left], nums[right]})
left++ // Move the left pointer to the right
right-- // Move the right pointer to the left
// Skip duplicate elements on the left side to avoid repeating the same triplet
for left < right && nums[left] == nums[left-1] {
left++
}
// Skip duplicate elements on the right side to avoid repeating the same triplet
for left < right && nums[right] == nums[right+1] {
right--
}
} else if sum > target {
// If the sum is greater than the target, move the right pointer to the left to decrease the sum
right--
} else if sum < target {
// If the sum is smaller than the target, move the left pointer to the right to increase the sum
left++
}
}
}
// Return the list of unique triplets
return results
}Copied!
Time and Space Complexity
Time Complexity
The time complexity of the given code is O(n^2). This is because there is a nested loop where the outer loop runs for n times (reduced by 2 to avoid unnecessary last iterations due to triplets), and within this loop, there are two pointers that are moving independently towards each other, which in total will lead to n iterations in the worst case. There are no nested loops inside the while loop, so the inner operations are constant time notwithstanding the while conditions which are also O(n). Multiplying these together gives us n * n = n^2, hence O(n^2).
Space Complexity
The space complexity of the code is O(log n) if we don’t take the output space into consideration, which would be O(n). The space complexity arises due to the space used by the sorting algorithm, which is typically O(log n) for the commonly used algorithms like QuickSort or MergeSort in many standard programming libraries.