Problem Statement: 3Sum
Description: Given an integer array nums, your task is to find all unique triplets in the array that sum up to zero.
Constraints:
3 <= nums.length <= 3000-10^5 <= nums[i] <= 10^5
Example 1:
Input: nums = [-1, 0, 1, 2, -1, -4]
Output: [[-1, -1, 2], [-1, 0, 1]]
Example 2:
Input: nums = []
Output: []Example 3:
Input: nums = [0, 1, 1]
Output: []Approach:
- Sorting: First, sort the array. Sorting helps in efficiently checking for triplets using the two-pointer technique, as it allows you to easily avoid duplicates and quickly adjust the sum by shifting pointers.
- Two-pointer Technique:
- Fix one element at a time and use two pointers to find the other two elements such that their sum with the fixed element equals zero.
- After sorting, the array becomes easier to manage with two pointers. One pointer starts from the element just after the fixed element, and the other starts from the end of the array. The sum of the three elements (fixed element, left pointer, and right pointer) is checked.
- If the sum is zero, add the triplet to the result.
- If the sum is less than zero, move the left pointer rightward to increase the sum.
- If the sum is greater than zero, move the right pointer leftward to decrease the sum.
- Skip duplicates to ensure each triplet is unique.
- Time Complexity: O(n^2), where
nis the length of the input array. Sorting the array takes O(n log n), and the two-pointer search for each element takes O(n) time. - Space Complexity: O(1), excluding the space used by the input and output.
Code Implementation in Different Languages:
C:
#include <stdio.h>
#include <stdlib.h>
void threeSum(int* nums, int numsSize) {
qsort(nums, numsSize, sizeof(int), compare);
for (int i = 0; i < numsSize - 2; i++) {
if (i > 0 && nums[i] == nums[i-1]) continue; // Skip duplicates
int left = i + 1, right = numsSize - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
printf("[%d, %d, %d]\n", nums[i], nums[left], nums[right]);
while (left < right && nums[left] == nums[left+1]) left++; // Skip duplicates
while (left < right && nums[right] == nums[right-1]) right--; // Skip duplicates
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
}
int compare(const void* a, const void* b) {
return (*(int*)a - *(int*)b);
}
int main() {
int nums[] = {-1, 0, 1, 2, -1, -4};
int size = sizeof(nums) / sizeof(nums[0]);
threeSum(nums, size);
return 0;
}
C++:
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<vector<int>> threeSum(vector<int>& nums) {
vector<vector<int>> result;
sort(nums.begin(), nums.end());
for (int i = 0; i < nums.size() - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates
int left = i + 1, right = nums.size() - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.push_back({nums[i], nums[left], nums[right]});
while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates
while (left < right && nums[right] == nums[right - 1]) right--; // Skip duplicates
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
int main() {
vector<int> nums = {-1, 0, 1, 2, -1, -4};
vector<vector<int>> result = threeSum(nums);
for (auto& triplet : result) {
for (int num : triplet) {
cout << num << " ";
}
cout << endl;
}
return 0;
}
Java:
import java.util.*;
public class Main {
public static List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> result = new ArrayList<>();
Arrays.sort(nums);
for (int i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates
int left = i + 1, right = nums.length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.add(Arrays.asList(nums[i], nums[left], nums[right]));
while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates
while (left < right && nums[right] == nums[right - 1]) right--; // Skip duplicates
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
public static void main(String[] args) {
int[] nums = {-1, 0, 1, 2, -1, -4};
List<List<Integer>> result = threeSum(nums);
for (List<Integer> triplet : result) {
System.out.println(triplet);
}
}
}
Python:
def threeSum(nums):
nums.sort()
result = []
for i in range(len(nums) - 2):
if i > 0 and nums[i] == nums[i - 1]: # Skip duplicates
continue
left, right = i + 1, len(nums) - 1
while left < right:
total = nums[i] + nums[left] + nums[right]
if total == 0:
result.append([nums[i], nums[left], nums[right]])
while left < right and nums[left] == nums[left + 1]: left += 1 # Skip duplicates
while left < right and nums[right] == nums[right - 1]: right -= 1 # Skip duplicates
left += 1
right -= 1
elif total < 0:
left += 1
else:
right -= 1
return result
# Example usage
nums = [-1, 0, 1, 2, -1, -4]
print(threeSum(nums))
JavaScript:
function threeSum(nums) {
nums.sort((a, b) => a - b);
let result = [];
for (let i = 0; i < nums.length - 2; i++) {
if (i > 0 && nums[i] === nums[i - 1]) continue; // Skip duplicates
let left = i + 1, right = nums.length - 1;
while (left < right) {
let sum = nums[i] + nums[left] + nums[right];
if (sum === 0) {
result.push([nums[i], nums[left], nums[right]]);
while (left < right && nums[left] === nums[left + 1]) left++; // Skip duplicates
while (left < right && nums[right] === nums[right - 1]) right--; // Skip duplicates
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
// Example usage
let nums = [-1, 0, 1, 2, -1, -4];
console.log(threeSum(nums));
C#:
using System;
using System.Collections.Generic;
class Program {
public static IList<IList<int>> ThreeSum(int[] nums) {
Array.Sort(nums);
List<IList<int>> result = new List<IList<int>>();
for (int i = 0; i < nums.Length - 2; i++) {
if (i > 0 && nums[i] == nums[i - 1]) continue; // Skip duplicates
int left = i + 1, right = nums.Length - 1;
while (left < right) {
int sum = nums[i] + nums[left] + nums[right];
if (sum == 0) {
result.Add(new List<int> { nums[i], nums[left], nums[right] });
while (left < right && nums[left] == nums[left + 1]) left++; // Skip duplicates
while (left < right && nums[right] == nums[right - 1]) right--; // Skip duplicates
left++;
right--;
} else if (sum < 0) {
left++;
} else {
right--;
}
}
}
return result;
}
static void Main() {
int[] nums = {-1, 0, 1, 2, -1, -4};
var result = ThreeSum(nums);
foreach (var triplet in result) {
Console.WriteLine($"[{string.Join(", ", triplet)}]");
}
}
}
Conclusion:
The 3Sum problem is efficiently solved by sorting the array first and then using the two-pointer technique. This approach ensures that the solution works in O(n^2) time, which is optimal for this type of problem. The key challenge is handling duplicates and ensuring that each triplet is unique.